Solution in c++ using deque


  • 1
    T
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> max;
            if (n==0) return max;
            
            queue<int> window;  // sliding window
            deque<int> maxs;    // deque holds the possible max values
            for (int i = 0; i < n; i++) {   
                window.push(nums[i]);
                // push max into deque
                while (!maxs.empty()) {
                    if (nums[i] > maxs.back()) maxs.pop_back();   // if this element is larger than the last in maxs[], remove the last element
                    else break; // otherwise stop
                }
                maxs.push_back(nums[i]); 
                // once the window is of size k, record the max value in this window, and then remove the 1st item from the window
                if (window.size() == k) {
                    max.push_back(maxs.front());
                    int out = window.front();
                    window.pop();
                    if (out == maxs.front()) maxs.pop_front();
                }
                
            }
            
            return max;
        }
        
    };

  • 0
    H

    the window can be removed~


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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.