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 可以向左和向右移動(不限方向,但仍需移到更高的建築物),如何修改?
- 如果要找「最近的」而非「最左的」共同可達建築物,如何調整?
- 如果建築高度可以動態修改,如何用線段樹支援在線查詢?