满足不等式的最大值

标签: 队列 数组 滑动窗口 单调队列 堆（优先队列）

难度: Hard

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

Submission

运行时间: 148 ms

内存: 51.7 MB

class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        res = - inf
        hq = []
        for x , y in points :
            while hq and x - hq[0][1] > k :
                heapq.heappop(hq)
            if hq :
                if (tmp := x + y - hq[0][0]) > res :
                    res = tmp
            heapq.heappush(hq, (x - y, x))
        return res

Explain

此题解主要利用堆（优先队列）来维护一个有效的点集，以寻找最大的表达式值。由于x是递增的，表达式可以重写为`yi + yj + |xi - xj|` = `yi + yj + (xj - xi)` = `(xj + yj) + (yi - xi)`。为了最大化该表达式，对于每个点j，我们想找到i使得`yi - xi`最大且满足`xj - xi <= k`。因此，我们用一个最大堆来维护所有可能的`(yi - xi)`值及其对应的`xi`。遍历每个点j时，我们从堆中移除所有不满足`xj - xi <= k`的点i，并检查堆顶元素以更新最大表达式值。

时间复杂度: O(n log n)

空间复杂度: O(n)


class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        res = -inf # 初始化结果为负无穷
        hq = [] # 初始化堆
        for x, y in points:
            # 移除所有x - x_i > k的点
            while hq and x - hq[0][1] > k:
                heapq.heappop(hq)
            # 如果堆不为空，更新结果
            if hq:
                # 计算当前点与堆顶点的表达式值
                if (tmp := x + y - hq[0][0]) > res:
                    res = tmp
            # 将当前点的(y - x, x)推入堆
            heapq.heappush(hq, (x - y, x))
        return res

Explore

选择维护`yi - xi`的最大值是因为表达式`yi + yj + |xi - xj|`可以重写为`(xj + yj) + (yi - xi)`。其中，对于每个固定的点j，`xj + yj`是一个已知的常数，因此为了最大化整个表达式，需要最大化`(yi - xi)`。这样，可以通过维护`(yi - xi)`的最大值来确保对于任意的j，总是能找到最优的i来最大化整个表达式的值。

在题目的代码中，堆实际存储的是`(y - x, x)`，而不是`(x - y, x)`。这可能是题目描述中的一个错误。存储`(y - x, x)`是为了能够在堆中以最大堆的方式维护`yi - xi`的最大值，这对应于最大化所需表达式的一部分。如果我们错误地存储了`(x - y, x)`，将会导致寻找最大值的逻辑错误，因为这样维护的是`xi - yi`的最大值，而不是题目要求的`yi - xi`。

一旦从堆中移除了所有`x - xi > k`的点，堆顶元素将是所有剩余元素中`yi - xi`最大的点。这确保了堆顶元素是在满足`xj - xi <= k`条件下`yi - xi`值最大的点。因此，堆顶元素是满足条件下的最优点i。

在题解中，确实考虑了堆可能为空的情况。在处理每个点时，首先会移除不满足条件的堆元素，然后检查堆是否为空。如果堆为空，意味着没有任何元素可以用来形成有效的表达式值，因此在这种情况下不会更新结果。只有当堆非空时，才会根据堆顶元素计算可能的最大表达式值并更新结果。这确保了算法的正确性和鲁棒性。