Title Description

Given an array num and the size k of the sliding window, please find the maximum value in all sliding windows.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Position {maximum value of sliding window
---------------               -----
[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

Please define a queue and implement the function max_value gets the maximum value in the queue and requires the function max_value,push_back and pop_ The average sharing time complexity of front is O(1).

If the queue is empty, pop_front and max_value ， need to return - 1

Example 1:

Input:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
Output: [null,null,null,2,1,2]
Example 2:

Input:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
Output: [null,-1,-1]

thinking

The maximum value of sliding window is nothing more than a fixed length queue, and its maximum value is taken every time, so the maximum value problem of sliding window can be transformed into the maximum value problem of queue

How to save the maximum value of a queue?  

For example, for a queue like 2,1,3,4,5,4,4,2,1, its maximum values are 2,2,3,4,5,5,5,5,5

For ascending sequences, 1, 3, 4 and 5 actually need to be saved. Do we need to save the first element '2'? No, we can find that as long as there is an element larger than the previous element, the previous small element needs pop_back until we encounter '4', which is smaller than 5 and needs to be pushed_ Back(), because if '5' is popped, the next largest element is 4. Similarly, 2 after 4 also needs to be pushed_ Back, 1 behind 2 also needs to be pushed_ back.

We only need to maintain a non incremental double ended queue. Every time we push in a new element, we pop the existing elements smaller than the new element num[i]_ back. Until the queue is empty or encounters an element larger than nums[i] In this way, every time we take a large value (provided that it is not empty), we return deque front(). But we're in pop_ Note in the front () function -- when the front element of pop and deque When the front () elements are equal, deque pop().

See for specific implementation

code

#include<queue>
using namespace std;


class MaxQueue {
public:
    queue<int> que;
    deque<int> deq;
    MaxQueue() {

    }

    int max_value() {
        if(!deq.empty())
            return deq.front();
        else {
            return -1;
        }
    }

    void push_back(int value) {
        que.push(value);
        while (!deq.empty()&&value > deq.back()) {
            deq.pop_back();
        }
        deq.push_back(value);
    }

    int pop_front() {
        if (que.empty()) {
            return -1;
        }
        int temp = que.front();
        que.pop();
        if (temp == deq.front()) {
            deq.pop_front();
        }
        return temp;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

Maximum value of sliding window -- Thinking

If you understand the previous question, at least this question will not be without ideas. We maintain a double ended queue to store the maximum value of the current window, vector push_ back(deuque.front()). Then set two pointers, left and right, to point to the left boundary and the right boundary respectively. If the right boundary > size, it means the end return res.

The logic of our cycle is to deque first pop_ Back() removes those < num [right] elements and deque push_ back(nums[right]),vector. push_ Back (maximum value -- deque.front()), and judge whether the element removed on the left is equal to this maximum value. If it is also equal to the maximum value, we will remove deque back().

code

#include<vector>
#include<queue>
using namespace std;

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