题目描述

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

例如，如果输入数组 [2,3,4,2,6,2,5,1] 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为 [4,4,6,6,6,5]。

注意：

数据保证 k 大于 0，且 k 小于等于数组长度。

样例

输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

算法1

(单调双端队列) $O(n)$

1. 对于两个元素a和b, 如果a序号小, b序号大, 并且a < b, 那么a永远不可能成为滑动窗口最大值, 元素a可以立即被舍弃. 因此, 建立起一个单调下降的序列, 里面的元素有机会成为滑动窗口的最大值.
2. 另外, 滑动窗口的宽度是固定的, 如果序列中的最大值(最左边的)的序号过小了, 也应该立即舍弃.

时间复杂度

每一个元素入列一次, 出列最多一次, 因此, 时间复杂度是O(n)

Python 代码

from collections import deque

class Solution(object):
    def maxInWindows(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """

        L = deque()
        ans = []
        for i, e in enumerate(nums):
            while L and i - L[0] >= k:
                L.popleft()
            while L and nums[L[-1]] <= e:
                L.pop()
            L.append(i)
            if i >= k -1:
                ans.append(nums[L[0]])
        return ans