239. Sliding Window Maximum

發表於 | 分類於

problem

solution

  • time out 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> ret, window;
            int n = nums.size();
            for(int i=0;i<n;++i){
                window.push_back(nums[i]);
                if(window.size()>k) window.erase(window.begin());
                if(window.size() == k){
                    int mx = INT_MIN;
                    for(int w:window) mx = max(w, mx);
                    ret.push_back(mx);
                }
            }
            return ret;
        }
    };

  • monotonic queue 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class MonotonicQueue{
    private:
        deque<int> dq;
    public:
        int max(){
            return dq.front();
        }
        void push(int n){
            while(!dq.empty() && dq.back()<n){
                dq.pop_back();
            }
            dq.push_back(n);
            
        }
        void pop(int n){
            if( n== dq.front()) dq.pop_front();
        }
    };
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            MonotonicQueue mq;
            vector<int> ret;
            int n = nums.size();
            for(int i=0;i<n;++i){
                mq.push(nums[i]);
                if(i>k-1) mq.pop(nums[i-k]);
                if(i>=k-1) ret.push_back(mq.max());                  
            }
            return ret;
        }
    };

analysis

  • time complexity O(n)
  • space complexity O(k)