239. 滑动窗口的最大值

题目描述

思路 and Swift 题解

这道题是一道经典的单调栈模版题，实现的方法是利用双端队列来对单调栈进行维护，单调栈当中存储的是nums数组的下标，双端队列dq从队首到队尾的元素存储的是nums的下标，这些下标满足nums[i] > nums[j]，其中i > j。

基于这个单调栈，我们不难找出一次滑动窗口当中的最大值，队首元素下标所指向的nums数组当中的元素一定是最大的那一个。清楚思路之后，我们就需要重点关注单调栈的维护了。首先，在我们对nums数组进行遍历的过程中，我们需要确保当前遍历到的这个元素在队列当中是最小的，如果从队尾开始前面的元素比它还要小，这些元素都需要从队列当中删除。当前元素的下标插入到队列当中时，需要确保队列当中没有比它要小的元素，它是队尾元素，而它之前的下标对应的元素比它都要大。

与此同时，由于滑动窗口的窗口大小是固定的，因此我们需要在每次循环都判断一下队首对应的下标是不是已经在滑动窗口之外了，如果是的话，就需要将队首的下标从对头移出队列。尽管队首下标对应的在nums当中的元素是当前队列当中最大的，但由于它已经不在滑动窗口当中了，我们不再需要它了。

经过队首和队尾的整理，现在我们可以顺利地将当前元素的下标插入到队列当中了。插入之后，我们需要判断一下当前遍历的下标是否大于等于滑动窗口的大小，如果是的话，就需要将当前双端队列队首下标对应的元素插入到答案数组ans当中，它就是当前滑动窗口的最大值；否则，不统计答案。

有了完整的思路，我们就可以使用 Swift 来解题了。有几个需要注意的点：首先，在使用for-in对nums遍历时，如果想要取到当前索引的元素的下标，需要使用nums数组的enumerated()方法，并使用元组(i, num)来对每一次循环体进行接收：

for (i, num) in nums.enumerated() {
		// statements
}

其次，在 Swift 当中，Array对象具有内置的removeLast()和removeFirst()方法，可以将数组的尾部和头部元素从数组当中原地移除。同时，Array具有内置的last属性，可以返回数组当中最后一个对象的可选值（是可选值的原因在于，数组可能是空的，此时没有最后一个元素）。

了解上述 Swift 语法之后，我们就可以开始编写代码解决这道问题了：

class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var dq = [Int]()
        var ans = [Int]()

        for (i, num) in nums.enumerated() {
            while dq.count > 0 && nums[dq.last!] < nums[i] {
                dq.removeLast()
            }
            while dq.count > 0 && dq[0] <= i - k {
                dq.removeFirst()
            }
            dq.append(i)
            if i >= k - 1 {
                ans.append(nums[dq[0]])
            }
        }

        return ans
    }
}