Leetcode 239. Sliding Window Maximum (pythonc++)

题目：

解法：deque实现的单调队列

关于单调队列的解释：https://medium.com/algorithms-and-leetcode/monotonic-queue-explained-with-leetcode-problems-7db7c530c1d6
举个例子来说明单调队列，现在有个递减的单调队列[6,4,3]：

• 新元素为2，队列变为[6,4,3,2]
• 新元素为5，队列变为[6,5]，4，3，2被踢走了
• 新元素为7，队列变为[7]，6，4，3，2被踢走了
  递增则更新逻辑反过来即可

对于这道题目，单调队列使用python中的deque来实现，因为根据题意，当头部元素也就是最大值不在滑窗内的时候，需要去除这个头部元素。又要更新尾部的元素，所以需要双向。
同时，我们还不能用元素的值直接构建单调队列，因为我们需要判断之前的最大值还在不在当前滑窗内。
具体步骤如下：

• 构建deque，deque中的元素为nums的index，队列中index对应的值递减
• 对每一步滑窗，进行clean_deque，包括判断当前deque的头部元素是否在滑窗内，从队尾取出小于新元素的值

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:n = len(nums)if n*k==0:return []if k==1:return numsdef clean_deque(i):# 判断当前最大值还在不在滑窗内，不在的话就移除，这步必须要在下一步前面if deq and deq[0]==i-k:deq.popleft()# 去除队尾比新元素小的值的indexwhile deq and nums[i]>nums[deq[-1]]:deq.pop()deq = collections.deque()ans = []ans.append(max(nums[:k]))for i in range(k):clean_deque(i)deq.append(i)for i in range(k,n):clean_deque(i)deq.append(i)ans.append(nums[deq[0]])return ans

C++版本：

class Solution {
    
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> deq;int n = nums.size();for (int i=0;i<k;i++){
    while(!deq.empty()&&nums[i]>nums[deq.back()]) deq.pop_back();deq.push_back(i);}vector<int> ans;for (int i=k;i<n;i++){
    ans.push_back(nums[deq.front()]);if (deq.front()==i-k) deq.pop_front();while(!deq.empty()&&nums[i]>nums[deq.back()]) deq.pop_back();deq.push_back(i);}ans.push_back(nums[deq.front()]);return ans;}
};

复杂度分析：O(N)。仔细观察就可以发现，每个元素都会被添加到deque一次，然后被删除一次，所以是O(N)

follow up

如果是个2D matrix，来做2维的sliding window maximum应该怎么做。这个就相当于是max pooling了。

做法还是基于1维的sliding window maximum，先对每行做1维sliding window maximum，再对每列做sliding window maximum，这样的效果和用一个kernel去滑动是一模一样的