题目大意：
满足不等式的最大值
给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。
请你找出 yi + yj + |xi – xj| 的 最大值，其中 |xi – xj| <= k 且 1 <= i < j <= points.length。
题目测试数据保证至少存在一对能够满足 |xi – xj| <= k 的点。
示例 1：
输入：points = [[1,3],[2,0],[5,10],[6,-10]], k = 1 输出：4 解释：前两个点满足 |xi - xj| <= 1 ，带入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。 没有其他满足条件的点，所以返回 4 和 1 中最大的那个。
示例 2：
输入：points = [[0,0],[3,0],[9,2]], k = 3 输出：3 解释：只有前两个点满足 |xi - xj| <= 3 ，带入方程后得到值 0 + 0 + |0 - 3| = 3 。
提示：
- 2 <= points.length <= 10^5
- points[i].length == 2
- -10^8 <= points[i][0], points[i][1] <= 10^8
- 0 <= k <= 2 * 10^8
- 对于所有的1 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1499
解题思路分析：
我们首先看下题目给出的公式：
sum = yi + yj + |xi - xj|;
因为xj一定大于xi，因此公式可以变形为：
sum = yi + yj + (xj - xi);
继续变形可得：
sum = (yi - xi) + (yj + xj);
上面的公式我们可以理解为两个部分，前半部分是一个点的纵坐标减去横坐标，后半部分是一个点的纵坐标加上横坐标。解题时，我们采取滑动窗口（双指针）方式来解题，初始时，左指针位于数组下标为0处，右指针位于下标为1处。此时如果右指针横坐标与左指针横坐标之差大于k，那么我们需要向右移动一位左指针来缩小两者之间的差值。注意如果移动后左右指针位于同一位置的话，由于区间内至少要保证拥有2个元素，所以右指针也需向右侧移动一位。
反之，如果右指针横坐标与左指针横坐标之差小于等于k，此时右指针代表当前点，我们计算出当前点横坐标与纵坐标之和(yj + xj)。然后再在[left, right)区间，即右指针到左指针下标减一范围内找到一个最大的(yi – xi)，这两者的和即是当前区间内最大sum。并使用该sum更新全局最大sum。然后右指针向右移动一格后继续重复上述步骤，直到右指针越界为止。
这样问题就剩下如何在一个区间内快速找到一个最大值(yi – xi)。关于这个问题，我们在之前的文章中介绍过：LEETCODE 239. Sliding Window Maximum 解题思路分析。最简单的方式是采用一个双向队列，使用递减方式保存区间内的值，此时队列头部的元素一定是区间内最大值。详细解法可以参考leetcode 239这道题目。
实现代码：
public int findMaxValueOfEquation(int[][] points, int k) {
// 返回结果
int res=Integer.MIN_VALUE;
// 左右指针
int left=0,right=1;
// 用于保存区间内最大值的queue
Deque<Integer> dq = new LinkedList<>();
// 将[left, right)区间内元素加入到queue
dq.offerLast(points[0][1]-points[0][0]);
while(right<points.length){
if(points[right][0]-points[left][0]>k){ // 两点的x坐标差大于k
// 将左指针指向元素移除区间
// 如果queue中的最大值等于左指针指向点的纵横坐标差，
if(dq.size()>0&&points[left][1]-points[left][0]==dq.peekFirst()){
dq.pollFirst(); // 将最大值移除queue
}
left++; // 左指针加一
if(right==left){ // 如果左右指针相同
dq.clear(); // 清空queue
// 将[left, right)区间内元素加入到queue
dq.offerLast(points[left][1]-points[left][0]);
right++; // 右指针加一
}
}else{ // 两点的x坐标差小于等于k
// 计算当前sum：queue中最大值加上当前点横纵坐标和
int sum=dq.peekFirst()+(points[right][1]+points[right][0]);
res=Math.max(res,sum); // 更新全局最大值
// 将当前元素加入Queue，
// 加入之前，先poll出所有小于当前元素的值
while(dq.size()>0&&points[right][1]-points[right][0]>dq.peekLast()){
dq.pollLast();
}
// 将当前元素加入Queue，
dq.offerLast(points[right][1]-points[right][0]);
right++; // 右指针加一
}
}
return res;
}本题解法执行时间为16ms。
Runtime: 16 ms, faster than 66.43% of Java online submissions for Max Value of Equation.
Memory Usage: 86.3 MB, less than 100.00% of Java online submissions for Max Value of Equation.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1499-max-value-of-equation-解题思路分析/