LeetCode 题解工作台
满足不等式的最大值
给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [x i , y i ] ，并且在 1 的前提下， x i j 总成立。 请你找出 y i + y j + |x i - x j | 的 最大…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 滑动窗口（状态滚动更新）
答案摘要
题目要求 $y_i + y_j + |x_i - x_j|$ 的最大值，其中 $i \lt j$，并且 $|x_i - x_j| \leq k$。由于 是严格单调递增的，那么： $$
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个数组 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 <= 105points[i].length == 2-108 <= xi, yi <= 1080 <= k <= 2 * 108- 对于所有的
1 <= i < j <= points.length，均有xi < xj。 xi构成一个严格递增序列。
解题思路
方法一：优先队列（大根堆）
题目要求 的最大值，其中 ，并且 。由于 是严格单调递增的，那么：
因此，对于当前遍历到的点 ，我们只需要找到前面所有满足 的点 中 的最大值，再加上当前的 即可。而 的最大值，我们可以使用优先队列（大根堆）来维护。
具体地，我们定义一个优先队列（大根堆） ，堆中每个元素是一个二元组 。
当我们遍历到点 时，如果堆 不为空，并且 ，那么循环将堆顶元素弹出，直到堆为空或者满足 。此时，堆顶元素 即为所有满足 的点中 的最大值，此时更新答案 。
然后，我们将点 加入堆中，继续遍历下一个点，直到遍历完整个数组 。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
ans = -inf
pq = []
for x, y in points:
while pq and x - pq[0][1] > k:
heappop(pq)
if pq:
ans = max(ans, x + y - pq[0][0])
heappush(pq, (x - y, x))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of how to maintain a sliding window.
- question_mark
Check if the candidate correctly uses a priority queue for efficient lookups.
- question_mark
Evaluate if the candidate handles the constraint |xi - xj| <= k appropriately while iterating.
常见陷阱
外企场景- error
Failing to properly manage the sliding window size could lead to incorrect results.
- error
Not using the priority queue effectively might result in inefficient or incorrect computation of the maximum value.
- error
Ignoring the constraint |xi - xj| <= k could cause invalid pairs to be considered.
进阶变体
外企场景- arrow_right_alt
Increase the problem's complexity by adding additional constraints on the y-values of points.
- arrow_right_alt
Consider modifying the equation to include additional terms or weights for each point.
- arrow_right_alt
Allow for dynamic updates to the points array and re-calculate the maximum value accordingly.