1499. Max Value of Equation

deque O(n) time O(n) space
先把equation拆成后边（x+y）和前边（x-y）之差，即(x_j + y_j) - (x_i - y_i)，对于每个(x_j + y_j)只需要知道前边最小的(x_i - y_i)即可，又因为有一个限制条件|x_i - x_j| <= k，说明需要用sliding window，参考239. Sliding Window Maximum用deque维护一个x_i - y_i的升序，每次先把不符合限制条件|x_i - x_j| <= k的i从前边剔除，然后计算结果，再插入j并在尾部剔除较大的不符合要求的下标以保持升序
另外要注意如果k过小，有可能没有结果

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        int res = INT_MIN;
        deque<int> q;
        for (int n = size(points), i = 0; i < n; ++i) {
            while (!q.empty() && points[i][0] - points[q.front()][0] > k) {
                q.pop_front();
            }
            if (!q.empty()) {
                res = max(res, points[i][0] + points[i][1] - (points[q.front()][0] - points[q.front()][1])); // 注意这道题一定要先计算再push新数，因为i < j
            }
            while (!q.empty() && points[q.back()][0] - points[q.back()][1] >= points[i][0] - points[i][1]) {
                q.pop_back();
            }
            q.push_back(i);
        }
        return res;
    }
};