1499. Max Value of Equation

题目信息

题号:

1499

难度:

Hard

主题:

单调队列、计算几何、滑动窗口

原题:

LeetCode 1499

重点:

点按横坐标严格递增排列;选择 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。