239 滑动窗口最大值

一、题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

二、题解

思路： 单调队列。用双端队列存下标，并保证队列中对应的 nums 值从队头到队尾单调递减。遍历时：

  1. 队头下标若已滑出窗口（<= i - k）则从队头移除；
  2. 队尾元素若小于当前 nums[i]，说明它不可能再成为最大值，从队尾弹出；
  3. 把当前下标加入队尾；
  4. 当窗口形成（i >= k - 1）后，队头即为当前窗口最大值的下标。

每个下标至多入队、出队一次，因此整体是线性的。

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;

        // 结果数组长度是 n - k + 1
        int[] ans = new int[n - k + 1];

        // 双端队列，里面存的是下标，不是元素值
        // 队列会保持 nums[下标] 从大到小
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {

            // 1. 移除已经滑出窗口的下标
            // 当前窗口范围是 [i - k + 1, i]
            // 如果队头下标 <= i - k，说明它已经不在窗口里了
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // 2. 保持队列单调递减
            // 如果当前 nums[i] 比队尾元素大，
            // 那么队尾元素以后不可能成为最大值，可以删掉
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // 3. 把当前元素下标加入队列
            deque.offerLast(i);

            // 4. 当窗口形成后，队头就是当前窗口最大值的下标
            if (i >= k - 1) {
                ans[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return ans;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(k)O(k)

评论