LeetCode.239.滑动窗口最大值（困难）

题目

LeetCode.239.滑动窗口最大值（困难）

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

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

题解

题解1：暴力

暴力法很好想。

• 枚举滑动窗口所有起始位置。
• 遍历滑动窗口内所有元素，记录最大值。

设数组长度为n，滑动长度长度为k，时间复杂度O(n * k)。

class Solution {
    /**
     * 暴力法，时间复杂度O(n*k)
     */
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val n = nums.size
        if (n == 0) return intArrayOf()
        val answer = IntArray(n - k + 1)
        var j = 0
        for (start in 0..(n - k)) {
            val end = start + k - 1
            var max = Int.MIN_VALUE
            for (i in start..end) {
                max = Math.max(max, nums[i])
            }
            answer[j++] = max
        }
        return answer
    }
}

解法2：单调队列

时间优化

暴力法的问题在于有很多从左到右重复的遍历判断。

如果有办法在滑动窗口移动的时候，就可以知道滑动窗口最大值，这样时间复杂度就可以减少到O(n - k)。

思路

滑动窗口向右移动时，会在末尾增加一个数，同时开头减少一个数，这个过程很像队列的入队和出队。

在比较新增和减少的元素对滑动窗口最大值的影响，可以发现：

• 如果新增的元素比之前的元素都大，那么之前的元素肯定不会是最大，不用考虑。
• 如果新增的元素大小位于之前元素的中间水平：
  • 那么之前的元素中比新增元素小的元素肯定是肯定不会最大，而且新增元素是比新增元素小的元素在后移除出滑动窗口的。
  • 新增元素现在虽然不是最大，但是滑动窗口右移后，之前最大的元素就不存在了，新增的这个元素可能又是最大。

所以滑动窗口的队列只需要存储单调递减的元素。

复杂度

• 时间复杂度O(n - k)：滑动窗口要移动n - k次。
• 空间复杂度O(k)：单调队列最多存储滑动窗口中所有元素。

import java.util.*

class Solution {
    /**
     * 维护一个队列，仅存放滑动窗口内的数字，每次向队尾插入数字前，先从队首依次检查并删除小于新插入的元素，这样队首始终是滑动窗口的最大值
     * 由于只会遍历数组依次，因此时间复杂度O(n)，用一个队列存储滑动窗口内的元素，最多存储k个，因此空间复杂度是O(k)
     */
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val n = nums.size
        if (n == 0) return intArrayOf()
        if (k == 1) return nums
        val answer = IntArray(n - k + 1)
        val queue = MonotonicQueue()
        for (i in 0 until n) {
            if (i < k - 1) queue.enqueue(nums[i])
            else {
                queue.enqueue(nums[i])
                answer[i - k + 1] = queue.max()
                queue.dequeue(nums[i - k + 1])
            }
        }
        return answer
    }

    /**
     * 单调递减的队列
     */
    class MonotonicQueue() {
        /**
         * 用双端队列模拟单调递减队列
         */
        private val deque: Deque<Int> = ArrayDeque<Int>()

        /**
         * 将[num]放入队尾，同时移除队列中比[num]小的数
         */
        fun enqueue(num: Int) {
            // 原队列已经保持单调递减，队尾小于新元素就出队
            while (deque.isNotEmpty() && deque.peekLast() < num) {
                deque.pollLast()
            }
            // 新元素入队到队尾
            deque.offerLast(num)
        }

        /**
         * 队首如果是[num]就删除
         */
        fun dequeue(num: Int) {
            if (deque.isNotEmpty() && deque.peekFirst() == num) {
                deque.pollFirst()
            }
        }

        /**
         * 返回队列中最大值
         */
        fun max(): Int {
            return deque.peekFirst()
        }
    }
}