Hard

题目描述

给你一个数组 points ，其中包含 2D 平面上点的坐标，按 x 值排序，其中 points[i] = [xi, yi] 且对于所有 1 <= i < j <= points.length 都有 xi < xj。同时给你一个整数 k。

返回等式 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。
没有其他点对满足条件，所以返回 max(4, 1) = 4。

示例 2：

输入：points = [[0,0],[3,0],[9,2]], k = 3
输出：3
解释：只有前两个点的 x 值绝对差小于等于 3，得到值 0 + 0 + |0 - 3| = 3。

约束条件：

  • 2 <= points.length <= 10^5
  • points[i].length == 2
  • -10^8 <= xi, yi <= 10^8
  • 0 <= k <= 2 * 10^8
  • 对于所有 1 <= i < j <= points.length，都有 xi < xj
  • xi 形成严格递增序列

解题思路

这是一个滑动窗口与优先队列结合的问题。

核心观察： 由于数组按 x 坐标排序，对于点 j，我们要找满足 xj - xi <= k 的点 i（其中 i < j）使得 yi + yj + (xj - xi) 最大。

数学变换： 等式可以重写为：yi + yj + (xj - xi) = (yi - xi) + (yj + xj)

对于固定的点 j，(yj + xj) 是常数，我们需要最大化 (yi - xi)。

算法思路：

  1. 使用优先队列（最大堆）维护所有可能的点 i 的 (yi - xi) 值
  2. 遍历每个点 j，首先移除队列中不满足距离约束的点（xj - xi > k）
  3. 如果队列非空，用队首元素（最大的 yi - xi）计算当前的等式值
  4. 将当前点加入队列供后续使用

优化细节：

  • 队列存储 [yi - xi, xi] 对，按第一个元素降序排列
  • 由于 x 坐标严格递增，只需检查队首元素是否满足距离约束

这种方法避免了 O(n²) 的暴力枚举，将时间复杂度优化到 O(n log n)。

代码实现

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        priority_queue<pair<int, int>> pq; // [yi - xi, xi]
        int maxVal = INT_MIN;
        
        for (auto& point : points) {
            int x = point[0], y = point[1];
            
            // Remove points that are too far
            while (!pq.empty() && x - pq.top().second > k) {
                pq.pop();
            }
            
            // Calculate equation value with the best previous point
            if (!pq.empty()) {
                maxVal = max(maxVal, pq.top().first + y + x);
            }
            
            // Add current point for future calculations
            pq.push({y - x, x});
        }
        
        return maxVal;
    }
};

class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        import heapq
        
        heap = []  # max heap using negative values: [-(yi - xi), xi]
        max_val = float('-inf')
        
        for x, y in points:
            # Remove points that are too far
            while heap and x - heap[0][1] > k:
                heapq.heappop(heap)
            
            # Calculate equation value with the best previous point
            if heap:
                max_val = max(max_val, -(heap[0][0]) + y + x)
            
            # Add current point for future calculations
            heapq.heappush(heap, [-(y - x), x])
        
        return max_val

public class Solution {
    public int FindMaxValueOfEquation(int[][] points, int k) {
        var pq = new PriorityQueue<(int diff, int x), int>(
            Comparer<int>.Create((a, b) => b.CompareTo(a))
        );
        int maxVal = int.MinValue;
        
        foreach (var point in points) {
            int x = point[0], y = point[1];
            
            // Remove points that are too far
            while (pq.Count > 0 && x - pq.Peek().x > k) {
                pq.Dequeue();
            }
            
            // Calculate equation value with the best previous point
            if (pq.Count > 0) {
                maxVal = Math.Max(maxVal, pq.Peek().diff + y + x);
            }
            
            // Add current point for future calculations
            pq.Enqueue((y - x, x), y - x);
        }
        
        return maxVal;
    }
}

var findMaxValueOfEquation = function(points, k) {
    let maxVal = -Infinity;
    let deque = [];
    
    for (let j = 0; j < points.length; j++) {
        while (deque.length > 0 && points[j][0] - points[deque[0]][0] > k) {
            deque.shift();
        }
        
        if (deque.length > 0) {
            let i = deque[0];
            maxVal = Math.max(maxVal, points[i][1] + points[j][1] + points[j][0] - points[i][0]);
        }
        
        while (deque.length > 0 && points[deque[deque.length - 1]][1] - points[deque[deque.length - 1]][0] <= points[j][1] - points[j][0]) {
            deque.pop();
        }
        
        deque.push(j);
    }
    
    return maxVal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)每个点最多进出优先队列一次，每次操作 O(log n)
空间复杂度O(n)优先队列最多存储 n 个点

相关题目