剑指Offer59-I题目分析

解题思路：

设窗口区间为[i,j]，最大值为xj。当窗口向前移动一格，则区间变为[i+1,j+1]，即添加了nums[j+1]，删除了nums[i]。

暴力法：遍历整个窗口区间获得最大值$x_{j+1}=max(nums(i+1),\cdots,num(j+1))$

根据以上分析，暴力法的时间复杂度为$O((n-k+1)k)\approx O(nk)$

设数组nums的长度为$n$，则共有$(n-k+1)$个窗口；
获取每个窗口最大值需线性遍历，时间复杂度为$O(k)$。

本题难点：如何在每次窗口滑动后，将”获取窗口内最大值”的时间复杂度从$O(k)$降低到$O(1)$。

单调队列：遍历数组时，每轮保证单调队列deque;

deque内仅包含窗口内的元素-》每轮窗口滑动移除了元素nums[i-1]，需将deque内的对应元素一起删除。
deque内的元素非严格递减-》每轮窗口活动添加了元素nums[j+1]，需将deque内所有<nums[j+1]的元素删除。

算法流程：

初始化：双端队列deque，结果列表res，数组长度n;
滑动窗口：左边界范围$i\in [1-k,n+1-k]$，右边界范围$j\in[0,n-1]$;
将nums[j]添加至deque尾部；
若已形成窗口(即i>=0):将窗口最大值(即队首元素deque[0])添加至列表res;
返回值：返回结果列表res;

复杂度分析：

时间复杂度$O(n)$:其中$n$为数组$nums$长度；线性遍历$nums$占用$O(n)$。每个元素最多仅入队和出队一次，因此单调队列$deque$占用$O(2n)$。
空间复杂度$O(n)$:双端队列$deque$中最多同时存储$k$个怨怒是(即窗口大小)。

代码：

class Solution:
    def maxSlidingWindow(self, nums, k):
        deque = collection.deque()
        res, n = [], len(nums)
        for i,j in zip(range(1-k, n+1-k), range(n)):
            # 删除deque中对应的nums[i-1]
            if i > 0 and deque[0] == nums[i-1]:
                deque.popleft()
            # 保持deque递减
            while deque and deque[-1] < nums[j]:
                deque.pop()
            deque.append(nums[j])
            # 记录窗口最大值
            if i >= 0:
                res.append(deque[0])
        return res

可以将”未形成窗口”和”形成窗口后”两个阶段拆分到两个循环里实现。代码虽变长，但减少了冗余的判断操作。

class Solution:
    def maxSlidingWindow(self, nums, k):
        if not nums or k == 0: return []
        deque = collections.deque()
        # 未形成窗口
        for i in range(k):
            while deque and deque[-1] < nums[i]:
                deque.pop()
            deque.append(nums[i])
        res = [deque[0]]
        # 形成窗口后
        for i in range(k, len(nums)):
            if deque[0] == nums[i-k]:
                deque.popleft()
            while deque and deque[-1] < nums[i]:
                deque.pop()
            deque.append(nums[i])
            res.append(deque[0])
        return res