88ms C++ solution. The test cases didn't show the power of dequeue.....


  • 0
    S

    Just simply keep and count the max value during sliding. If the count equals to 0, check the window again for the max value.

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            int i,j;
            int n = nums.size();
            int max = INT_MIN;
            int max_ct = 0;
            vector<int> rec;
            
            if (nums.size()==0) return rec;
            
            for (i=0; i<k; i++) 
                if (nums[i]>max)
                {
                    max = nums[i];
                    max_ct = 1;
                } else if (nums[i]==max)
                {
                    max_ct ++;
                }
                
            rec.push_back(max);
                
            for (j=k; j<n; j++)
            {
                if (nums[j-k]==max)
                {
                    max_ct --;
                }
                if (max_ct==0)
                {
                    max = INT_MIN;
                    for (i=j-k+1; i<=j; i++)
                        if (nums[i]>max)
                        {
                            max = nums[i];
                            max_ct = 1;
                        } else if (nums[i]==max)
                        {
                            max_ct ++;
                        }
                } else if (nums[j]>max)
                {
                    max = nums[j];
                    max_ct = 1;
                } else if (nums[j]==max)
                {
                    max_ct ++;
                }
                
                rec.push_back(max);
            }
            
            return (rec);
        }
    };

Log in to reply
 

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