1499. Max Value of Equation

You are given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, where points[i] = [xi, yi] such that xi < xj for all 1 <= i < j <= points.length. You are also given an integer k.

Return the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and 1 <= i < j <= points.length.

It is guaranteed that there exists at least one pair of points that satisfy the constraint |xi - xj| <= k.

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        int n = points.size(), l = 0, r = 1;
        vector<int> distance(n), y(n);
        for(int i = 1; i < n; i++) {
            distance[i] = points[i][0] - points[0][0];
            y[i] = points[i][1] + distance[i];
        }
        priority_queue<int> pq;
        multiset<int> rm;
        int res = INT_MIN;

        while(l < n) {
            bool remove = true;
            if(l == r) {r++; remove = false;}
            while(r < n and points[l][0] + k >= points[r][0]) {
                pq.push(y[r++]);
            }

            if(l != 0 and remove) rm.insert(y[l]);

            while(!pq.empty()) {
                if(rm.count(pq.top())) {
                    rm.erase(rm.find(pq.top()));
                    pq.pop();
                } else break;
            }

            if(!pq.empty()) res = max(res, points[l][1] + pq.top() - distance[l]);

            l++;
        }
        return res;
    }
};