239. 滑动窗口最大值

方法1：更新滑动窗口法（暴力遍历，超时）

滑动窗口没有完全进入数组时，把数据加入窗口中
窗口完全进入数组后，保存最大值，同时弹出窗口最左侧的元素（即，右边进，左边出，更新窗口），继续进行下一次循环

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        window=[]
        res=[]
        for i in range(len(nums)):
            if i-k+1<0: # 滑动窗口未完全进入数组，把元素添加到窗口中
                window.append(nums[i])
            else:
                window.append(nums[i])
                res.append(max(window)) # 记录窗口中最大值
                window.pop(0) # 弹出窗口最左边的元素
        return res

方法二：维护一个递减的单调队列

踩扁前面比他小的数
图片来自labuladong

给定一个数组 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

每次循环结束后，deque中存储的元素：

deque([1]) （前两次窗口未满）
deque([3]) （前两次窗口未满）
deque([3, -1])
deque([-1, -3]) （当前窗口中的元素为[3,-1,-3], 队列中最左边的元素queue[0]为nums[i - k + 1]，则把队头删掉；否则不满足queue[0] == nums[i - k + 1]，pop_num（）函数中if语句不执行，相当于不用删队头）
deque([5])
deque([5, 3])
deque([6])
deque([7])

双端队列中存储着压扁后剩下的结果（确保队列单调递减）
队列中的最大值有重复时，保留重复（只踩扁比它小的数，相同的不踩，确保次序一致）
之所以要判断queue[0] == n，是因为我们想删除的队头元素 n 可能已经被「压扁」了，这时候就不用删除了
- 若加进来的元素一直压不扁队头，但队列已满时，要删掉最左边的队头元素（如果已经压扁过了，那么queue[0] == nums[i - k + 1]不成立 ,不用删了）
  - 以滑动窗口位置在[6 5 4] 8 为例，当前i指向4时，现在的队列是[6 5 4] （5 和 4 都没能压扁6），窗口最大值为6。此时队头元素为nums[i - k + 1]，把队头 6 pop出去。队列变为[5 4]。此次循环结束
  - 现在要把8加进来，8把它们都压扁了，现在队列为[8],最大值为队首8, queue[0]并不等于nums[i - k + 1]（也就是5），if语句不执行,所以不用popleft

class Solution(object):
    def maxSlidingWindow(self, nums, k):

        def push_num(n):
            # 把元素n加入双端队列，小于n的元素被n踩扁
            while queue and queue[-1] < n:
                queue.pop()
            queue.append(n)

        def pop_num(n):
            # 把最左端的元素n弹出双端队列
            if queue[0] == n:
                queue.popleft()

        res = []
        from collections import deque
        queue = deque()
        for i in range(len(nums)):
            if i - k + 1 < 0: # 双端队列没有完全进入列表，则把该元素（以能否压扁的机制）加入队列
                push_num(nums[i])
            else:
                push_num(nums[i]) # 把该元素加入队列
                res.append(queue[0]) # 最左端为最大值
                pop_num(nums[i - k + 1]) # 删除位置为i-k+1的元素 （若已经被压扁了，则不用删了）
        return res

//#include <vector>
//#include <deque>
//#include <iostream>
//
//using namespace std;

class Solution {
private:
    vector<int> res;
    deque<int> q;
public:
    void push_num(int n) {
        while (!q.empty() && q.back() < n) {
            q.pop_back();
        }
        q.push_back(n);
    }

    void pop_num(int n) {
        if (q.front() == n) {
            q.pop_front();
        }
    }

    vector<int> maxSlidingWindow(vector<int> &nums, int k) {

        for (int i = 0; i < nums.size(); ++i) {
            if (i - k + 1 < 0) {
                push_num(nums[i]);
            } else {
                push_num(nums[i]);
                res.push_back(q.front());
                pop_num(nums[i - k + 1]);
            }
        }
        return res;
    }
};

//int main() {
//    Solution s;
//    vector<int> nums{1, 3, -1, -3, 5, 3, 6, 7};
//    int k = 3;
//    vector<int> ans = s.maxSlidingWindow(nums, k);
//    for (auto &i: ans) {
//        cout << i << "\t";
//    }
//}

其他写法：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        # 如果数组为空或 k = 0，直接返回空
        if not nums or not k:
            return []
        # 如果数组只有1个元素，直接返回该元素
        if len(nums) == 1:
            return [nums[0]]

        # 初始化队列和结果，队列存储数组的下标
        queue = []
        res = []

        for i in range(len(nums)):
            # 如果当前队列最左侧存储的下标等于 i-k 的值，代表目前队列已满。
            # 但是新元素需要进来，所以列表最左侧的下标出队列
            if queue and queue[0] == i - k:
                queue.pop(0)

            # 对于新进入的元素，如果队列前面的数比它小，那么前面的都出队列
            while queue and nums[queue[-1]] < nums[i]:
                queue.pop()
            # 新元素入队列
            queue.append(i)

            # 当前的大值加入到结果数组中
            if i >= k-1:
                res.append(nums[queue[0]])

        return res