Share my solution : c++, deque, 123ms


  • 0
    Z

    Using a dequeue to maintain the max number in the window. Using a queue to simulate the window sliding.
    When a number slides into the window, it will compare with the max number in the deque from back to front. If the new numberis bigger, then pop_back, till the back of deque is bigger than the new number. Then push_back new number.

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> ret;
            queue<int> q;
            deque<int> maxnum;
            int sz = nums.size();
            if(sz == 0) return {};
            if(sz <= k) {
                int retnum = INT_MIN;
                for(int i=0; i<sz; i++) retnum = max(retnum, nums[i]);
                return {retnum};
            }
            
            int idx = 0;
            for(; idx<k; idx++) {
                q.push(nums[idx]);
                while(!maxnum.empty() && maxnum.back()<nums[idx]) maxnum.pop_back();
                maxnum.push_back(nums[idx]);
            }
            while(idx<=sz) {
                ret.push_back(maxnum.front());
                if(idx == sz) break;
                int num = q.front();
                if(num == maxnum.front()) maxnum.pop_front();
                q.pop();
                q.push(nums[idx]);
                while(!maxnum.empty() && maxnum.back()<nums[idx]) maxnum.pop_back();
                maxnum.push_back(nums[idx]);
                idx++;
            }
            return ret;
        }
    };

Log in to reply
 

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