Neat and easy-understand c++ O(n) solution


  • 0
    Q
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> result;
            
            if (nums.empty() || k==0)
            return result;
            
            deque<int> maxElem;
            int p=0, q=-1;
            
            while(q<(int)nums.size())
            {
                int wLen= q-p+1;
                if (wLen==k)
                {
                   result.push_back(maxElem.front());
                   if (nums[p]==maxElem.front())
                   maxElem.pop_front();
                   
                   p++;
                }
                
                q++;
                if (q<(int)nums.size())
                {
                   while(!maxElem.empty() && nums[q]>maxElem.back())
                   maxElem.pop_back();
                   
                   maxElem.push_back(nums[q]);
                }
            }
            
            return result;
        }
    };

Log in to reply
 

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