HardRating 2456
1499. Max Value of Equation
arrayqueuesliding-windowheap-priority-queuemonotonic-queue
解題說明
Max Value of Equation
題目描述： 給定一組按 x 座標排序的點 points[i] = [xi, yi]，以及一個整數 k。找出滿足 |xi - xj| <= k 的一對點 (i, j)，使得 yi + yj + |xi - xj| 的值最大。
解題思路： 由於點按 x 排序且 i < j，所以 |xi - xj| = xj - xi。因此目標式變為 (yj + xj) + (yi - xi)。對於固定的 j，需要在 xj - xi <= k 的範圍內找到最大的 (yi - xi)。使用單調遞減佇列維護 (yi - xi) 的最大值，窗口條件為 xj - xi <= k。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個點最多進出佇列一次
空間複雜度：O(n) — 單調佇列最壞情況儲存 n 個元素
虛擬碼
1. Initialize monotonic deque dq (decreasing by yi - xi value)
2. For each point (xj, yj):
a. Remove points from front where xj - xi > k (out of window)
b. If dq non-empty, update result = max(result, yj + xj + dq.front().first)
c. Compute val = yj - xj
d. Remove points from back of dq where value <= val
e. Push {val, xj} to back of dq
3. Return result其他解法
方法二：優先佇列（Max Heap） 使用最大堆儲存 (yi - xi, xi)。每次取堆頂，如果 xj - xi > k 就彈出。時間複雜度 O(n log n)。
方法三：暴力枚舉 雙重迴圈枚舉所有滿足 |xi - xj| <= k 的點對。時間複雜度 O(n^2)，只適合小規模輸入。
延伸思考
- 如果點沒有按 x 座標排序，你會如何修改演算法？
- 如果要找的是最小值而非最大值，佇列的單調性需要如何改變？
- 如何將此方法推廣到三維空間中的類似問題？