1499. Max Value of Equation¶
题目信息¶
- 题号:
1499
- 难度:
Hard
- 主题:
单调队列、计算几何、滑动窗口
- 原题:
- 重点:
点按横坐标严格递增排列;选择
i < j且xj-xi <= k,最大化yi + yj + xj - xi
题目重述¶
给定平面点数组 points,其中 points[i] = [xi, yi],横坐标 xi 严格递增;另给定正整数 k。
选择两个不同点 i < j,要求 xj - xi <= k,并计算 yi + yj + |xi - xj|。请返回所有合法点对中的最大值。题目保证至少存在一对合法点。
2 <= points.length <= 10^5,坐标位于 [-10^8,10^8],1 <= k <= 2 * 10^8。
自建示例¶
窗口内点对按横坐标差贡献额外分数:
输入:points = [[0,1],[2,3],[3,-1]], k = 3
输出:6
解释:选择前两个点,结果为 1 + 3 + 2 = 6。
最大值也可能为负数:
输入:points = [[1,-2],[2,-3]], k = 1
输出:-4
解释:唯一合法点对的结果为 -2 - 3 + 1 = -4。