1499. 滿足不等式的最大值

思路

輸入一系列座標點 $(x,y)$ ，和限制 $k$ ， $x$ 軸經過排序，沒有重複。
找到滿足 $y_i+y_j+|x_i-x_j|$ 的最大值，
其中 $x_i-x_j \leq{k}$ 且 $1\leq{i}\leq{j}\leq\text{points.length}$ ，保證答案存在。

固定右邊界， $(x_i, y_i)$ 跟 $(x_j,y_j)$ 算出的答案 $y_j+\blue{y_i}+x_j-\blue{x_i}$ 。
移動左邊界到 $(x_{i+1},y_{i+1})$ 後，。

• 原先數值： $(x_j+y_j)+(y_i-x_i)$
• 後來數值： $(x_j+y_j)+(y_{i+1}-x_{i+1})$

獲得的要大於損失，移動右邊界才有意義，也就是說，
左邊界的 $y-x$ 要比原先的大，才有辦法讓總和更大。
因此，單調隊列當中時刻保留最大的 $y-x$ ，只有在 $x_i-x_j>k$ 而不符合條件的時候，才去隊列找替補。

程式碼

單調隊列 數組實現

class Solution {
private:
    static const int MX = 1e5 + 1;
    int dq[MX];
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        int n = points.size();
        int left = 0, right = 0;
        int res = INT_MIN;
        for(int i = 0; i < n; i++) {
            // 檢查左端是否滿足 xi - xj < k
            while(left != right && points[dq[left]][0] < points[i][0] - k) {
                left++;
            }

            // 更新答案，以當前座標為右邊界的最佳答案：xi + yi - xj + yj
            // 需要在加入隊列之前計算，避免自己跟自己配對
            if(left != right) {
                res = max(res, points[i][0] + points[i][1] - points[dq[left]][0] + points[dq[left]][1]);
            }

            // 新的座標加入，假如比最爛替補加的數值還要多，踢掉替補。
            // 加的數值是 yj - xj
            while(left != right && points[dq[right - 1]][1] - points[dq[right - 1]][0] <= points[i][1] - points[i][0]) {
                right--;
            }
            dq[right++] = i;

        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$