1499. Max Value of Equation

Return maximum value of the equation: yi + yj + |xi - xj| where |xi - xj| <= k

how find max (yi + yj + xi - xj) , 1 <= i < j <= points.length, so xi - xj is positive

fix j, is new incoming value yj + xj = max (-xi + yi)

think of mono queue, main a decreasing mono queue

decreasing mono queue 分兩個 case, 但 queue 還是放 index

1. pop last - in here, is (-xi + yi) ≤ nums[i]

2. pop first - |xi-xj| ≤ k

所以隊首都會是最大的

T: O(n)

S: O(n)

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int n = points.length;
        int res = Integer.MIN_VALUE;
        
        Deque<Integer> queue = new ArrayDeque<>();
        for (int j = 0; j < n; j++) {
            
            // valid is: xj - xi <= k
            while (!queue.isEmpty() && 
                   points[j][0] - points[queue.peekFirst()][0] > k) {
                queue.pollFirst();
            }
            
            // -xi + xj + (xj+yj)
            if (!queue.isEmpty()) {
                res = Math.max(
                    res, 
                    -points[queue.peekFirst()][0] + points[queue.peekFirst()][1] + points[j][0] + points[j][1]
                );
            }

            // try find larger -xj + xi
            while (!queue.isEmpty() && 
                   -points[queue.peekLast()][0] + points[queue.peekLast()][1] <= (-points[j][0] + points[j][1])) {
                queue.pollLast();
            }
            
            queue.offer(j);
        }
        return res;
    }
}

/*
Return maximum value of the equation:
yi + yj + |xi - xj| where |xi - xj| <= k

at least one pair of points that satisfy the constraint |xi - xj| <= k.


xi form a strictly increasing sequence.

[1,3] [2,0] 

[5,10][6,]


max (yi + yj + xi - xj)

fix j, is new incoming value
yj + xj = max (-xi + yi)



points[i][0]

*/