Leetcode1499满足不等式的最大值

问题分析

双端队列按照y-x的值从大到小组织，队列中存储点的编号。

如果y-x的值大于队列尾部元素的y-x值，则从尾部弹出元素。

如果当前点的x值与队列头部元素的x值之差大于k时，则从头部弹出元素。

求解代码

publicstaticintMAXN=100001;publicstaticint[][]deque=newint[MAXN][2];publicstaticinth,t;publicstaticintfindMaxValueOfEquation(int[][]points,intk){h=t=0;intn=points.length;intans=Integer.MIN_VALUE;for(inti=0,x,y;i<n;i++){x=points[i][0];y=points[i][1];while(h<t&&deque[h][0]+k<x){h++;}if(h<t){ans=Math.max(ans,x+y+deque[h][1]-deque[h][0]);}while(h<t&&deque[t-1][1]-deque[t-1][0]<=y-x){t--;}deque[t][0]=x;deque[t++][1]=y;}returnans;}