算法：滑动窗口里的最大值（ACM）

程序员三明治

发布于 2025-12-18 19:49:49

1010

文章被收录于专栏：码力up码力up

平时用leetcode刷的较多，突然改成acm还有点懵

自定义队列 `MyQueue` 的作用

使用双端队列（Deque）实现一个单调递减队列，确保队列头部始终是当前窗口的最大值。
方法细节：
- add(int val)：添加元素时，移除队列尾部所有小于 val 的元素（例如队列为 [3,1]，添加 2 时移除 1，变为 [3,2]），保持队列单调递减。
- poll(int val)：移除元素时，只有当被移除的值等于队列头部值时才弹出头部（例如队列为 [3,2]，移除 3 时弹出头部）。
- peek()：直接返回队列头部元素，即当前最大值。

`Solution` 的步骤

初始化：
- 如果输入数组长度小于等于 1，直接返回原数组（无滑动窗口）。
- 计算结果数组长度：len = heights.length - limit + 1，其中 limit 是窗口大小。
- 创建结果数组 res 和计数器 num。
处理初始窗口：
- 将数组前 limit 个元素添加到 MyQueue。
- 记录第一个窗口的最大值（通过 myqueue.peek()）。
滑动窗口：
- 从索引 i = limit 开始遍历数组：
  - 移除窗口最左边的元素（myqueue.poll(heights[i - limit])）。
  - 添加新元素（myqueue.add(heights[i])）。
  - 记录当前窗口最大值（res[num++] = myqueue.peek()）。
- 重复直到数组结束。

时间和空间复杂度

单调队列确保每个元素最多被添加和移除一次，平均时间复杂度为 O(n)，其中 n 是数组长度。
空间复杂度为 O(k)（k 是窗口大小），因为队列最多存储 k 个元素。

class MyQueue {
    Deque<Integer> deque = new LinkedList<>();
    //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
    //同时判断队列当前是否为空
    void poll(int val){
        if(!deque.isEmpty() && val == deque.peek()){
            deque.poll();
        }
    }
    //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
    //保证队列元素单调递减
    //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
    void add(int val){
        while(!deque.isEmpty() && val > deque.getLast()){
            deque.removeLast();
        }
        deque.add(val);
    }
    int peek() {
        return deque.peek();
    }
}
class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if(heights.length <= 1 ){ // 此处与卡哥代码里的不同 
            return heights;
        }
        //对结果数组进行初始化
        int len = heights.length - limit + 1;
        int[] res = new int[len];
        int num = 0;
        MyQueue myqueue = new MyQueue();
        //先将前k个放入队列
        for(int i = 0; i < limit; i++){
            myqueue.add(heights[i]);
        }
        res[num++] = myqueue.peek();
        for(int i = limit; i < heights.length; i++){
            //滑动窗口移除最前面的元素
            myqueue.poll(heights[i - limit]);
            //加入新元素
            myqueue.add(heights[i]);
            //记录最大值
            res[num++] = myqueue.peek();
        }
        return res;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-07-06，如有侵权请联系 cloudcommunity@tencent.com 删除

算法