【经典算法题】滑动窗口最大值

题目描述：Leetcode 0239 滑动窗口最大值

分析

• 本题的考点：单调队列。

• 本题是一个十分经典的题目。关于单调队列的讲解可以参考：网址。

• 注意这里使用的双端队列，因为两端都要弹出元素。

• 队列中存储的是元素对应的下标，这是因为我们要判断队首元素是否滑出滑窗，假设当前遍历到第i个元素，队首为q[hh]，如果i - q[hh] + 1 > k，说明队首元素已经滑出滑窗，需要弹出队首元素。

• 求区间最大值的话，这里的队列是严格单调递减的，原因可以参考网址。若当前考察元素为nums[i]，若有 n u m s [ q [ t t ] ] ≤ n u m s [ i ] nums[q[tt]] le nums[i] nums[q[tt]]≤nums[i]，则需要弹出队尾元素，直到不满足该条件或者队列为空，最后队列中插入nums[i]对应的下标i。

• 如果当前遍历到第i个元素且i>=k-1，说明滑窗中到达了k个元素，队首元素就是区间最大值。

代码

• C++

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        
        int n = nums.size();
        int q[n];
        int hh = 0, tt = -1;  // 手写队列
        vector res;
        for (int i = 0; i < nums.size(); i++) {
            if (hh <= tt && i - q[hh] + 1 > k) hh++;
            while (hh <= tt && nums[q[tt]] <= nums[i]) tt--;
            q[++tt] = i;
            if (i >= k - 1) res.push_back(nums[q[hh]]);
        }
        return res;
    }
};

• Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        int[] res = new int[nums.length - k + 1];
        int index = 0;
        Deque q = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            if (q.size() != 0 && i - q.getFirst() + 1 > k) q.removeFirst();  // 剔除过时的元素
            while (q.size() != 0 && nums[q.getLast()] <= nums[i]) q.removeLast();  // 删除队列中小于等于 当前元素 的元素的索引
            q.addLast(i);  // 添加新元素
            if (i >= k - 1) res[index++] = nums[q.getFirst()];
        }

        return res;
    }
}

时空复杂度分析

• 时间复杂度： O ( n ) O(n) O(n)，n为数组长度。

• 空间复杂度： O ( n ) O(n) O(n)。