原文链接: https://leetcode-cn.com/problems/max-value-of-equation

英文原文

You are given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, where points[i] = [xi, yi] such that xi < xj for all 1 <= i < j <= points.length. You are also given an integer k.

Return the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and 1 <= i < j <= points.length.

It is guaranteed that there exists at least one pair of points that satisfy the constraint |xi - xj| <= k.

 

Example 1:

Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
Output: 4
Explanation: The first two points satisfy the condition |xi - xj| <= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1.
No other pairs satisfy the condition, so we return the max of 4 and 1.

Example 2:

Input: points = [[0,0],[3,0],[9,2]], k = 3
Output: 3
Explanation: Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.

 

Constraints:

• 2 <= points.length <= 105
• points[i].length == 2
• -108 <= xi, yi <= 108
• 0 <= k <= 2 * 108
• xi < xj for all 1 <= i < j <= points.length
• xi form a strictly increasing sequence.

中文题目

给你一个数组 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 是严格递增的。

通过代码

高赞题解

解题思路

单调队列。

将原表达式进行处理为
$$ y_i + y_j + x_j - x_i = x_j + y_j + y_i - x_i $$
对于每个j而言，只需要找到其前面长度为k范围内的$y_i - x_i$的最大值即可。可以使用单调队列处理。

时间复杂度O(N)

个人博客

代码

typedef pair<int, int> PII;
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<PII> dq;
        dq.push_back({points[0][0], points[0][1] - points[0][0]});
        int ans = -2e9;
        for(int i = 1; i < points.size(); i ++) {
            
            while (dq.size() && points[i][0] - dq.front().first > k) dq.pop_front();
            if (dq.size()) ans = max(ans, dq.front().second + points[i][0] + points[i][1]);
            while (dq.size() && dq.back().second <= points[i][1] - points[i][0]) dq.pop_back();
            dq.push_back({points[i][0], points[i][1] - points[i][0]});
            // cout << ans << endl;
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
2921	7775	37.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言