アリスとボブに会える建物を探す

2940。アリスとボブに会える建物を探す

難易度: 難しい

トピック: 配列、二分探索、スタック、バイナリ インデックス付きツリー、セグメント ツリー、ヒープ (優先キュー)、単調スタック

正の整数の 0 インデックス付き 配列の高さが与えられます。heights[i] は i ^番目 の建物の高さを表します。

建物 i にいる人は、i

クエリ[i] = [a_i, b_i] である別の配列クエリも与えられます。 i ^番目 クエリでは、アリスは a_i を構築しており、ボブは b_i を構築しています。

配列 ans を返します。ここで、ans[i] は、i番目^{のクエリでアリスとボブが会うことができる}一番左の建物のインデックス

です。アリスとボブがクエリ i で共通の建物に移動できない場合は、ans[i] を -1 に設定します。

例 1:

• 入力:
高さ = [6,4,8,5,2,7]、クエリ = [[0,1],[0,3],[2,4],[3,4] 、[2,2]]
• 出力:
[2,5,-1,5,2]
• 説明:
  最初のクエリでは、heights[0]
2 番目のクエリでは、heights[0] 3 番目のクエリでは、アリスは他の建物に移動できないため、アリスはボブに会うことができません。
4 番目のクエリでは、高さ[3] 5 番目のクエリでは、アリスとボブはすでに同じ建物内にいます。
ans[i] != -1 の場合、ans[i] がアリスとボブに会える一番左の建物であることがわかります。
ans[i] == -1 の場合、アリスとボブに会える建物がないことがわかります。

例 2:

• 入力: 高さ = [5,3,8,2,6,1,4,6]、クエリ = [[0,7],[3,5],[5,2],[ 3,0],[1,6]]
• 出力: [7,6,-1,4,6]
• 説明: 最初のクエリでは、heights[0]
• 2 番目のクエリでは、高さ[3]
• 3 番目のクエリでは、ボブは他の建物に移動できないため、アリスはボブに会うことができません。
• 4 番目のクエリでは、heights[3]
• 5 番目のクエリでは、heights[1]
• ans[i] != -1 の場合、ans[i] がアリスとボブに会える一番左の建物であることがわかります。
• ans[i] == -1 の場合、アリスとボブに会える建物がないことがわかります。

制約:

• 1 4
• 1 9
• 1 4
• クエリ[i] = [a_i, b_i]
• 0 _i, b_i

ヒント:

1. 各クエリ [x, y] について、x > の場合、 y、x と y を入れ替えます。ここで、x
2. 各クエリ [x, y] について、x == y または heights[x]
3. それ以外の場合は、y
4. 各クエリのインデックス t を見つけるには、クエリを y の降順に並べ替えます。インデックス t を見つけるためにバイナリ検索できる単調スタックを維持しながらクエリを反復します。

解決策:

この問題では、開始時の建物と移動ルールを考慮して、アリスとボブが会うことができる一番左の建物を決定する必要があります。各クエリには、建物の高さに基づいて待ち合わせ場所を見つけることが含まれます。これは、動きに制約があり、効率的な計算が必要なため、困難です。

重要なポイント

1. アリスとボブは、現在の建物よりも高さが厳密に高い場合、別の建物に移動できます。
2. クエリごとに、左端の有効なミーティング ポイントを検索します。そのような建物が存在しない場合は -1 を返します。
3. 制約により、単純な O(n²) アプローチよりも優れた解決策が求められます。

アプローチ

1. 所見:

   • a == b の場合、アリスとボブはすでに同じ建物にいます。
   • 高さ[a]の場合
   • それ以外の場合は、最小の建物インデックス t を見つけます > b ここで:
     • 高さ[a]
     • heights[b]

2. 単調スタックを使用した最適化:

   • 単調スタックは、アリスとボブが移動できる有効な建物を効率的に追跡するのに役立ちます。建物は高さが降順になるようにスタックに追加され、高速なバイナリ検索が可能になります。

3. クエリの並べ替え:

   • クエリを b の降順に並べ替えて、インデックスが大きい建物を最初に処理します。これにより、より高いインデックスからより低いインデックスに移動するときにスタックを効率的に構築できます。

4. スタック上の二分探索:

   • 各クエリに対して、単調スタックで二分探索を使用して、条件を満たす最小のインデックス t を見つけます。

計画

1. 2 つのインデックス (b) の大きい方に基づいてクエリを降順に並べ替えます。
2. 有効なインデックスの単調スタックを維持しながら、配列を逆方向に走査します。
3. 各クエリについて、自明なケース (a == b または heights[a]
4. 自明ではない場合は、スタックを使用して二分探索で左端の有効な建物を見つけます。
5. 元のクエリ順序で結果を返します。

解決策の手順

1. クエリの前処理:

   • 一貫性を保つために、各クエリで
   • クエリを b で降順に並べ替えます。

2. クエリの反復:

   • 配列をトラバースするときに単調スタックを維持します。
   • 各クエリについて:
     • a == b の場合、答えは b です。
     • 高さ[a]の場合
     • それ以外の場合は、スタックを使用して最小の有効なインデックス t > を見つけます。 b.

3. スタック上の二分探索:

   • 二分探索を使用して、heights[t] > を満たすスタック上の最小のインデックス t をすばやく見つけます。高さ[a].

4. 元の注文を復元:

   • 結果を元のクエリ インデックスにマッピングします。

5. 結果を返します。

このソリューションを PHP で実装してみましょう: 2940。アリスとボブに会える建物を探す

<?php /**
 * @param Integer[] $heights
 * @param Integer[][] $queries
 * @return Integer[]
 */
function leftmostBuildingQueries($heights, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $queries
 * @return array
 */
private function getIndexedQueries($queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $stack
 * @param $a
 * @param $heights
 * @return mixed|null
 */
private function findUpperBound($stack, $a, $heights) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

class IndexedQuery {
    public $queryIndex;
    public $a; // Alice's index
    public $b; // Bob's index

    /**
     * @param $queryIndex
     * @param $a
     * @param $b
     */
    public function __construct($queryIndex, $a, $b) {
        $this->queryIndex = $queryIndex;
        $this->a = $a;
        $this->b = $b;
    }
}

// Test the function
$heights = [6, 4, 8, 5, 2, 7];
$queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
print_r(leftmostBuildingQueries($heights, $queries));

$heights = [5, 3, 8, 2, 6, 1, 4, 6];
$queries = [[0, 7], [3, 5], [5, 2], [3, 0], [1, 6]];
print_r(leftmostBuildingQueries($heights, $queries));
?>

説明：

1. クエリの並べ替え: クエリは、大きいインデックスを最初に処理するために b で降順に並べ替えられます。これにより、処理中に単調スタックを更新できます。
2. 単調スタック: スタックは、アリスとボブが出会うことができる建物のインデックスを追跡するために使用されます。以前に確認された建物よりも高い高さの建物のみをスタックに保持します。
3. 二分検索: 各クエリに答えるとき、二分検索を使用して、条件が満たされる最小のインデックス t を効率的に見つけます。

チュートリアルの例

入力：

• 身長 = [6,4,8,5,2,7]
• クエリ = [[0,1],[0,3],[2,4],[3,4],[2,2]]

プロセス：

1. 並べ替えクエリ:

   • インデックス付きクエリ: [(2,4)、(3,4)、(0,3)、(0,1)、(2,2)]

2. 単調スタックの構築:

   • 最も高いインデックスから開始して、スタックにインデックスを追加します。
     • インデックス 5: スタック = [5]
     • インデックス 4: スタック = [5, 4]
     • ...

3. クエリ処理:

   • クエリ [0,1] の場合、高さ [0]
   • ...

出力：

[2、5、-1、5、2]

時間計算量

1. クエリの並べ替え: O(Q log Q) ここで、Q はクエリの数です。
2. 単調スタック構造: O(N) ここで、N は高さの長さです。
3. 各クエリの二分検索: O(Q log N).

全体: O(N Q log (Q N)).

出力例

入力:

$heights = [6, 4, 8, 5, 2, 7];
$queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];

出力:

print_r(findBuilding($heights, $queries)); // [2, 5, -1, 5, 2]

このアプローチは、単調スタックと二分探索を活用することで、大きな制約を効率的に処理します。これにより、正確性を維持しながら最適なクエリ処理が保証されます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がアリスとボブに会える建物を探すの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。