1499. 满足不等式的最大值 (opens new window)

1.单调队列

分析：将不等式变形为 yi+yj+|xi-xj| = (xj+yj)+(yi-xi) ，其中j>i，从而将问题转化为从小于j横坐标的点中，找到y坐标值减去x坐标值的最大值坐标点 。

使用单调队列实现，队列存储二元组【xi，yi-xi】，队列维护时需要保证yi-xi从队首到队尾是递减的：

• 计算最大不等式：对于当前坐标i来说，如果队首最大值与当前坐标不满足k间距约束，那么队首元素出队列。直到保证此时队首元素一定能够与当前坐标i构成一个最大不等式。
• 当前元素入队：考虑当前元素i入队后，队列中哪些元素在后续的搜索是无用的？需要将队列中所有y-x差小于当前坐标结果的元素j移出队列。因为在后续搜索的过程当中，相比于坐标 j ，当前坐标i一定会是更优解。

根据问题求解的需要确定队列元素维护时单调的属性。本题中既然要求j节点之前最大的yi-xi，那么队列就维护y-x的单调性。因为遍历时是从左向右遍历，天然满足搜索时索引单调。虽然队列中不能保证x坐标是单调的，但是当前坐标j合并的坐标只需要保证①它的y-x是最大的②满足k约束这两个条件即可。

int res=Integer.MIN_VALUE;
        Deque<int[]>  queue=new LinkedList<>();
        for(int i=0;i<points.length;i++){
            int sum=points[i][0]+points[i][1];
            int sub=points[i][1]-points[i][0];
            //先移除所有x坐标不满足条件的坐标
            while(!queue.isEmpty()&&points[i][0]-queue.peekFirst()[0]>k) queue.pollFirst();
            while(!queue.isEmpty()&&sub>=queue.peekLast()[1]){
                res=Math.max(res,sum+queue.pollLast()[1]);
            }
            if(!queue.isEmpty())res=Math.max(res,sum+queue.peekFirst()[1]);
            queue.offerLast(new int[]{points[i][0],sub});

        }
        return res;