# 1499. Max Value of Equation
###### tags: `Leetcode` `Hard` `Deque`
Link: https://leetcode.com/problems/max-value-of-equation/
## 思路
要求的是 $y_i+y_j+|x_i-x_j|$
如果我们固定$j$再加上points是根据x sorted的所以相当于我们求的是$y_i-x_i+y_j+x_j$
也就是要在$|x_i-x_j|<k$的前提下找到$y_i-x_i$的最大值
是一个典型的**sliding window maximum**的问题
解法是用deque
如果$|x_i-x_j|$不符合条件的话就从前面poll出去一个element(deque里面从前往后是按照x的顺序)
我们保持的是一个满足首尾元素$|x_i-x_j|<k$的窗口。队列中保持递减的序列。任何新进来的元素，如果$-x+y$比队尾元素要大，说明队尾的元素就不再有任何利用的价值（又旧又小，永远不会被用到），那么队尾元素都可以弹出。
## Code

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        Deque<int[]> q = new ArrayDeque<>();
        int ans = Integer.MIN_VALUE;
        for(int[] point:points){
            while(!q.isEmpty() && point[0]-q.getFirst()[0]>k){
                q.pollFirst();
            }
            if(!q.isEmpty()){
                ans = Math.max(ans, point[1]+q.getFirst()[1]+point[0]-q.getFirst()[0]);
            }
            while(!q.isEmpty() && q.getLast()[1]-q.getLast()[0]<point[1]-point[0]){
                q.pollLast();
            }
            q.addLast(point);
        }
        return ans;
    }
}