HardRating 2327

2940. Find Building Where Alice and Bob Can Meet

arraybinary-searchstackbinary-indexed-treesegment-treeheap-priority-queuemonotonic-stack

解題說明

Find Building Where Alice and Bob Can Meet

題目描述：給定建築物高度陣列 heights 和查詢陣列 queries。每個查詢 [a, b] 要求找到最左邊的建築物索引 i，使得 i >= a, i >= b，且 heights[i] > heights[a] 和 heights[i] > heights[b]（Alice 和 Bob 都能到達）。Alice 從 a 出發只能向右移到更高的建築物，Bob 從 b 出發同理。

解題思路：離線處理 + 最小堆。首先簡化：若 a == b，答案為 a。若 a > b 則交換使 a < b。若 heights[b] > heights[a]，答案為 b（Bob 已在較高建築物且 b >= a）。

否則需要在 b 右邊找到第一個高度 > max(heights[a], heights[b]) 的建築物。將這類查詢按 b 排序，使用最小堆離線處理：從左到右掃描 heights，對於每個位置 i，檢查堆中是否有查詢的 threshold < heights[i]，若是則 i 就是答案。

C++ 解法

複雜度分析

時間複雜度：O((n + m) log m) — 每個查詢最多進出堆各一次，每次操作 O(log m)

空間複雜度：O(n + m) — 暫存的查詢和最小堆

虛擬碼

1. For each query [a, b] (ensure a <= b):
   a. If a == b or heights[b] > heights[a]: answer = b
   b. Else: store as pending query at position b with threshold = max(heights[a], heights[b])
2. Scan heights left to right (position i = 0 to n-1):
   a. Add all pending queries at position i to min-heap (keyed by threshold)
   b. While heap top's threshold < heights[i]:
      - This query's answer = i (first building taller than both)
      - Pop from heap
3. Remaining queries in heap have no answer (-1)
4. Return answers

其他解法

線段樹 + 離線法：建立高度的線段樹，支援範圍最大值查詢。對每個待解查詢，在 [b+1, n-1] 中二分搜尋第一個高度大於 threshold 的位置。時間 O((n + m) log n)。
單調棧法：從右到左建立單調遞減棧。對每個查詢，在棧上二分搜尋第一個大於 threshold 的位置。需要離線按右端點處理。時間 O((n + m) log n)。

延伸思考

如果 Alice 和 Bob 可以向左和向右移動（不限方向，但仍需移到更高的建築物），如何修改？
如果要找「最近的」而非「最左的」共同可達建築物，如何調整？
如果建築高度可以動態修改，如何用線段樹支援在線查詢？

Find Building Where Alice and Bob Can Meet — CaffeCode