239-滑动窗口的最大值

LeetCode 239. Sliding Window Maximum

LeetCode-239

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[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

method: 单调队列

要维护单调，可以用栈，但是又要维护大小，就需要从头部弹出元素，所以用双端队列

1. 类似于单调栈，维护一个从队首到队尾单调递减（不增）的队列
   也就是，如果后面的元素比队尾元素大，队尾元素就要出队，直到队空

2. 其次，要保证队内元素不超过k个，所以要判断新插入元素和队首元素的距离，所以入队的是元素的下标

nums = {3, 2, 1, 0}, k=3
前3个遍历完后队列中的元素为：3 2 1，最大元素为3
i=3时，0小于队列最后一个元素，所以队列不用从后面弹出，而且要把0插入到队列末尾
但是此时i-q.front()=3>=k，如果再把0插入队列就变成4个了，所以必须先把队头的3弹出，再把0插入末尾

判断队列里的元素个数应该是：i - q.front() + 1 > k
等价于：i - q.front() > k - 1
等价于：i - q.front() >= k

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> q;
    for (int i = 0; i < k; i++) {
        while (!q.empty() && nums[q.back()] < nums[i])
            q.pop_back();
        q.push_back(i);
    }
    vector<int> res;
    res.push_back(nums[q.front()]);
    for (int i = k; i < nums.size(); i++) {
        while (!q.empty() && nums[q.back()] < nums[i])
            q.pop_back();   // 保持单调
        if (!q.empty() && i - q.front() >= k)
            q.pop_front();  // 判断队列里的元素是否超过k个
        q.push_back(i);
        res.push_back(nums[q.front()]); // 队首元素就是最大值
    }
    return res;
}