LeetCode - 239. 滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 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

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法
swift

/**
 暴力解法
 外层循环数组，内层循环窗口k，找到最大值
 时间复杂度为O(n*k)
 空间复杂度为O(1)
 提交LeetCode超时
 */
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
    // 过滤边界
    guard nums.count > 0 else {
        return []
    }
    var results = [Int]()
    for i in 0..<nums.count-k+1 {
        var maxValue = nums[i]
        for j in 1..<k {
            maxValue = max(maxValue, nums[i+j])
        }
        results.append(maxValue)
    }
    return results
}

/**
 双端队列
 单调递减队列，保证队列头部始终是最大值
 尾部插入数据，判断当前索引值 ？ 尾部索引值，小于：尾插；否则，移除尾部数据
 判断队列内的元素个数是否超出窗口k， 当前索引 - 队列头部索引 ？k 超出，移除队列头部
参考题解：https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/
 时间复杂度为O(n)
 空间复杂度为O(n)
 */
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
    // 过滤边界
    guard nums.count > 0 else {
        return []
    }
    var results = [Int](repeating: 0, count: nums.count-k+1)
    // 双端队列，单调递减，保证头部为最大值
    var deque = [Int]()
    var currentIndex = 0
    for i in 0..<nums.count {
        // 当前索引值 大于等于 队列尾部的值，移除尾部索引
        while !deque.isEmpty && nums[i] >= nums[deque.last!]  {
            deque.removeLast()
        }
        deque.append(i)
        // 队列头部的索引超出当前窗口，移除头部索引
        while deque.first! <= i - k {
            deque.removeFirst()
        }
        // 数组索引小于 k-1 的元素不需要保存记录
        if i >= k - 1 {
            results[currentIndex] = nums[deque.first!]
            currentIndex += 1
        }
    }
    return results
}

GitHub：https://github.com/huxq-coder/LeetCode