剑指 Offer 59 - I. 滑动窗口的最大值

[Hinsverson]

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

 

提示：

• 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[Hinsverson]

思路：使用队列维护最大值，减少比较次数

遍历待考察数组，遍历到的当前元素就是我 for 我 in nums { 第一步：移除队列中，所有比我小的值。 第二步：把我添加到队列中。 第三步：将队列中的第一个值（也就是最大值）放到一个数组中（最终方法要返回的数组）。 第四步：为下一个窗口做准备。（移除下一个窗口以外的元素） }

class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        let nums = nums
        var res = [Int]()
        var queue = [Int]()

        for (index, value) in nums.enumerated() {
            // 第一步：移除队列中，比我小的值（对应的索引）
            while queue.count > 0 {
                if value > nums[queue.last!] {
                    queue.removeLast()
                }else {
                    break
                }
            }
            // 第二步：把我（的索引）添加到队列
            queue.append(index)
            // 第三步：获得当前窗口最大值
            if index >= k - 1 {
                res.append(nums[queue.first!])
            }
            // 第四步：为下一个窗口做准备
            if index - queue.first! >= k - 1 {
                queue.removeFirst()
            }

        }
        return res
    }

}