找到愛麗絲和鮑伯可以見面的建築物

2940。找到愛麗絲和鮑伯可以見面的建築物

難度：難

主題：陣列、二分查找、堆疊、二元索引樹、線段樹、堆疊（優先權佇列）、單調堆疊

給你一個0索引正整數高度數組，其中heights[i]代表第i^第建築物的高度。

如果一個人在建築物 i 中，當且僅當 i

您還會得到另一個陣列查詢，其中 requests[i] = [a_i, b_i]。在第 i^th 查詢中，Alice 正在建構 a_i，而 Bob 正在建構 b_i。

回傳一個陣列 ans，其中 ans[i] 是 最左邊建築物的索引，Alice 和 Bob 可以在第 i^th 查詢中相遇。如果 Alice 和 Bob 無法在查詢 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]
• 解釋： 在第一個查詢中，Alice 和 Bob 可以移動到 2 號樓，因為 heights[0]
• 在第二個查詢中，Alice 和 Bob 可以移動到 5 號樓，因為 heights[0]
• 在第三個查詢中，Alice 無法見到 Bob，因為 Alice 無法移動到任何其他建築物。
• 在第四個查詢中，Alice 和 Bob 可以移動到 5 號樓，因為 heights[3]
• 在第五個查詢中，Alice 和 Bob 已經在同一棟大樓。
• 對於 ans[i] != -1，可以證明 ans[i] 是 Alice 和 Bob 可以見面的最左邊的建築物。
• 對於 ans[i] == -1，可以證明不存在 Alice 和 Bob 可以見面的建築物。

範例2：

• 輸入： 高度= [5,3,8,2,6,1,4,6]，查詢= [[0,7],[3,5],[5,2],[ 3,0],[1,6]]
• 輸出： [7,6,-1,4,6]
• 解釋： 在第一個查詢中，Alice 可以直接移動到 Bob 的建築物，因為 heights[0]
• 在第二個查詢中，Alice 和 Bob 可以移動到 6 號樓，因為 heights[3]
• 在第三個查詢中，Alice 無法見到 Bob，因為 Bob 無法移動到任何其他建築物。
• 在第四個查詢中，Alice 和 Bob 可以移動到 4 號樓，因為 heights[3]
• 在第五個查詢中，Alice 可以直接移動到 Bob 的建築物，因為 heights[1]
• 對於 ans[i] != -1，可以證明 ans[i] 是 Alice 和 Bob 可以見面的最左邊的建築物。
• 對於 ans[i] == -1，可以證明不存在 Alice 和 Bob 可以見面的建築物。

約束：

• 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. 否則，我們需要找到最小的索引 t 使得 y
4. 要找出每個查詢的索引 t，請按 y 的降序對查詢進行排序。迭代查詢，同時維護單調堆疊，我們可以對其進行二分搜尋以查找索引 t。

解：

這個問題需要根據愛麗絲和鮑伯的起始建築物和移動規則確定最左邊的建築物，愛麗絲和鮑伯可以在其中相遇。每個查詢都涉及根據建築物高度找到交匯點。由於移動的限制和高效計算的需要，這是一個挑戰。

要點

1. 愛麗絲和鮑伯可以移動到另一棟建築，前提是建築物的高度嚴格大於當前建築。
2. 對於每個查詢，找到最左邊的有效集合點，如果不存在這樣的建築物，則返回-1。
3. 這些限制需要一個比簡單的 O(n²) 方法更好的解決方案。

接近

1. 觀察結果：

   • 如果 a == b，則 Alice 和 Bob 已經在同一棟大樓了。
   • 如果高度[a]
   • 否則，找出最小的建築索引 t >其中：
     • 高度[a]
     • heights[b]

2. 使用單調堆疊最佳化：

   • 單調堆疊有助於有效追蹤 Alice 和 Bob 可以移動到的有效建築物。建築物添加到堆疊中的方式確保高度按遞減順序排列，從而實現快速二進制搜尋。

3. 查詢排序：

   • 依 b 的降序對查詢進行排序，以先處理索引較大的建築物。這確保了當我們從較高的索引移動到較低的索引時，我們可以有效地建立堆疊。

4. 堆疊上的二分查找：

   • 對於每個查詢，在單調堆疊上使用二分查找來找到滿足條件的最小索引t。

計畫

1. 根據兩個索引 (b) 中較大的一個按降序對查詢進行排序。
2. 向後遍歷數組，同時維護有效索引的單調堆疊。
3. 對於每個查詢，檢查簡單情況（a == b 或 heights[a]
4. 對於重要的情況，使用堆疊透過二分搜尋找到最左邊的有效建築物。
5. 依照原始查詢順序傳回結果。

解決步驟

1. 預處理查詢：

   • 確保每個查詢中的 a
   • 依 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 處：Stack = [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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是找到愛麗絲和鮑伯可以見面的建築物的詳細內容。更多資訊請關注PHP中文網其他相關文章！