239. Sliding Window Maximum - cocoder39/coco39_LC GitHub Wiki

239. Sliding Window Maximum

Notes 2022:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = collections.deque()
        output = []
        for i, num in enumerate(nums):
            while queue and num > nums[queue[-1]]:
                queue.pop()
            queue.append(i)
            
            while queue[0] <= i - k:
                queue.popleft()
            
            if i >= k - 1:
                output.append(nums[queue[0]])
        return output

============================================================================ in the monotonic queue, the size of maxq is always no greater than numq In our problem, we maintain the numq.size() to be k, so the overall space complexity is O(k), time complexity is O(n) where n is size of input array

class MaxQueue {
public:
    void push(int x) {
        numq.push(x);
        while (! maxq.empty() && maxq.back() < x) {
            maxq.pop_back();
        }
        maxq.push_back(x);
    }    
    
    void pop() {
        if (maxq.front() == numq.front()) {
            maxq.pop_front();
        }
        numq.pop();
    }
    
    int getMax() {
        return maxq.front();
    }
private:
    queue<int> numq;
    deque<int> maxq;
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        MaxQueue mq;
        for (int i = 0; i < nums.size(); i++) {
            if (i >= k) {
                mq.pop();
            }
            mq.push(nums[i]);
            if (i >= k - 1) {
                res.push_back(mq.getMax());
            }
        }
        return res;
    }
};

concise version

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq;
        for (int i = 0; i < nums.size(); i++) {
            if (i >= k && dq.front() == nums[i - k]) { //pop
                dq.pop_front();
            } 
            
            while (! dq.empty() && dq.back() < nums[i]) { //push
                dq.pop_back();
            }
            dq.push_back(nums[i]);
            
            if (i >= k - 1) { //getMax
                res.push_back(dq.front());
            }
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️