跳至主要內容

LeetCode 1499. 满足不等式的最大值——滑动窗口+单调队列的组合优化

老张2026/4/30大约 7 分钟

LeetCode 1499. 满足不等式的最大值——滑动窗口+单调队列的组合优化

适读人群：Java 高级工程师、备战大厂 Hard 题的同学 | 阅读时长：约25分钟 | 难度：困难

开篇故事

这是本系列的压轴题，也是整个单调栈/队列专题里综合难度最高的一道。

表面上是个数学题，展开化简后，变成了一个「在滑动窗口内，维护某个线性表达式的最大值」的问题。这恰好是单调双端队列（Monotonic Deque） 最经典的应用场景——和第 239 题「滑动窗口最大值」同一类型，但表达式更复杂，需要先做数学推导再套模板。

这道题展示了算法竞赛里一种很重要的解题思路：先做数学变换简化问题，再套合适的数据结构。如果上来就套暴力或者直接上堆，会发现很难在约束范围内通过。

一、题目解析

题目描述：

给你一个数组 points，其中 points[i] = [xi, yi]，并且所有 xi 互不相同，所有 xi 已经是 升序排列 的。

请你找出 yi + yj + |xi - xj| 的最大值，其中 |xi - xj| <= k（即 j 和 i 的 x 坐标差不超过 k）。

注意： 可以按任意顺序取两个点，但 xi 已经排好序。

示例：

输入：points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
输出：4
解释：选取 (1,3) 和 (2,0)，结果 = 3+0+|1-2| = 4

输入：points = [[0,0],[3,0],[9,2]], k = 3
输出：3

约束：

  • 2 <= points.length <= 10^5
  • 1 <= k <= 10^8
  • -10^8 <= yi <= 10^8

二、数学推导（关键！）

对于 i < j（j 在 i 右边），由于 xi < xj，所以 |xi - xj| = xj - xi。

目标值展开：

yj + yi + |xi - xj| = yj + yi + xj - xi
                    = (yj + xj) + (yi - xi)

所以对于固定的 j，目标是最大化 (yj + xj) + max(yi - xi)，其中 i 满足 xj - xi <= k，即 xi >= xj - k。

因为 xi 是升序的，满足约束的 i 就是一个滑动窗口：xi 在 [xj-k, xj-1] 范围内的所有点。我们需要在这个窗口内找 yi - xi 的最大值。

结论： 这是一个「滑动窗口内的最大值」问题，套单调队列（双端队列）模板。

三、解法一：暴力双循环

思路分析

对所有满足 |xi - xj| <= k 的对 (i, j)，直接计算目标值。

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int n = points.length;
        int result = Integer.MIN_VALUE;
        
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (points[j][0] - points[i][0] <= k) {
                    int val = points[j][1] + points[i][1] + points[j][0] - points[i][0];
                    result = Math.max(result, val);
                }
            }
        }
        
        return result;
    }
}

复杂度分析

  • 时间复杂度：O(n²)。n=10^5 时，10^10 操作，必然超时。
  • 空间复杂度：O(1)。

四、解法二：最大堆（优先队列）

思路分析

对于固定的 j，需要找满足 xj - xi <= k 的所有 i 中，yi - xi 最大的。

用最大堆维护「可以和 j 配对的所有 i 的 yi - xi 值」，每次 j 右移时，弹出所有 xj - xi > k 的旧元素。

import java.util.*;

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int n = points.length;
        int result = Integer.MIN_VALUE;
        
        // 最大堆，存 [yi - xi, xi]，按 yi-xi 降序
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );
        
        for (int[] point : points) {
            int xj = point[0], yj = point[1];
            
            // 移除不满足 xj - xi <= k 的旧元素
            while (!maxHeap.isEmpty() && xj - maxHeap.peek()[1] > k) {
                maxHeap.poll();
            }
            
            if (!maxHeap.isEmpty()) {
                // (yj + xj) + max(yi - xi)
                result = Math.max(result, yj + xj + maxHeap.peek()[0]);
            }
            
            // 将当前点加入堆
            maxHeap.offer(new int[]{yj - xj, xj});
        }
        
        return result;
    }
}

复杂度分析

  • 时间复杂度：O(n log n)。最坏情况每个元素出入堆一次。
  • 空间复杂度：O(n)。

五、解法三（最优）：单调双端队列

核心思想

最大堆在移除过期元素时效率不够：堆顶不一定是过期的，只能一个一个检查。单调双端队列（Monotonic Deque）可以在 O(1) 均摊时间内完成所有操作：

  • 队列头部：窗口内 yi - xi 最大的元素（因为单调递减）
  • 移除过期元素：从队列头部检查 x 坐标，超出窗口就弹出（O(1)）
  • 维护单调性：从队列尾部弹出 yi - xi 更小的元素（这些元素不可能成为最优解）

完整代码

import java.util.*;

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int n = points.length;
        int result = Integer.MIN_VALUE;
        
        // 单调递减双端队列，存 [yi-xi, xi]
        // 队列头部是窗口内 yi-xi 最大的（我们需要的）
        // 队列尾部是最近加入的（yi-xi 最小的）
        Deque<int[]> deque = new ArrayDeque<>();
        
        for (int[] point : points) {
            int xj = point[0], yj = point[1];
            
            // 1. 移除超出窗口的队头元素（x 坐标差 > k）
            while (!deque.isEmpty() && xj - deque.peekFirst()[1] > k) {
                deque.pollFirst();
            }
            
            // 2. 用队头（当前窗口内 yi-xi 最大）更新结果
            if (!deque.isEmpty()) {
                result = Math.max(result, yj + xj + deque.peekFirst()[0]);
            }
            
            // 3. 维护单调性：弹出队尾中 yi-xi 更小的元素
            //    因为新加入的 yj-xj 更大，之前那些小的永远不会成为最优
            while (!deque.isEmpty() && deque.peekLast()[0] <= yj - xj) {
                deque.pollLast();
            }
            
            // 4. 将当前点加入队尾
            deque.offerLast(new int[]{yj - xj, xj});
        }
        
        return result;
    }
}

手动模拟

以 points = [[1,3],[2,0],[5,10],[6,-10]], k=1 为例：

jxjyjyj-xj队头操作result
0132空无更新，加入(2,1)-
120-2(2,1)xj-xi=1<=1，result=0+2+2=4；2>=-2，不弹尾；加(−2,2)4
25105(2,1)xj-xi=4>1，弹(2,1)；剩(−2,2)，xj-xi=3>1，弹；队空不更新4
2加(5,5)后队:(5,5)
36-10-16(5,5)xj-xi=1<=1，result=max(4,-10+6+5)=4；5>=-16不弹；加(-16,6)4

最终：4，正确！

复杂度分析

  • 时间复杂度：O(n)。每个元素最多入队出队各一次，总操作 2n，均摊 O(n)。
  • 空间复杂度：O(n)。单调队列大小。

六、举一反三

「滑动窗口内的最大/最小值」→ 单调双端队列：

题目单调队列的内容
239. 滑动窗口最大值窗口内的下标（按值单调递减）
1499. 满足不等式最大值窗口内 yi-xi（单调递减）
862. 和至少为K的最短子数组前缀和（单调递增）

七、踩坑实录

坑一：数学推导的前提是 i < j（xi < xj）

因为 points 按 xi 升序排列，遍历 j 时，所有在 j 左边的 i 都有 xi < xj，所以 |xi - xj| = xj - xi 这个化简是正确的。

如果数组不是升序的，需要先排序，或者把绝对值分两种情况处理。

坑二：步骤2和步骤3的顺序不能颠倒

必须先用队头更新 result（步骤2），再维护单调性并加入当前点（步骤3）。如果先维护单调性，可能把当前点自己作为候选比较，然后又把它用于更新 result，逻辑混乱。

严格说，当前点 j 不能和自己配对，所以先查询再插入是正确的顺序。

坑三：队列头部移除时用「>」，不是「>=」

条件 xj - deque.peekFirst()[1] > k 意味着距离严格大于 k 才移除。题目要求 |xi - xj| <= k，等于 k 时还是合法的，不能移除。

八、总结

1499 是整个系列的完美收官题，把单调栈/队列的思维推到了极致：

  1. 数学化简：把复杂的目标函数变换成「滑动窗口内线性函数的最大值」
  2. 单调队列模板：队头是窗口最优解，队尾维护单调性
  3. O(n) 时间：相比暴力 O(n²) 有质的提升

20 篇系列走到这里，覆盖了单调栈（601-608）、优先队列与堆（609-616）、差分数组与扫描线（617-619）和组合优化（620）四个子主题。希望每一篇都能给你带来一些新的思考角度。

编辑此页
最近更新:
贡献者: xiaozhangge