LeetCode题解——Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,

Given nums = 

[1,3,-1,-3,5,3,6,7]

, and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
      

Therefore, return the max sliding window as 

[3,3,5,5,6,7]

.

Note: 

You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

方法一：顺序判断

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        if(nums.size()<=1||k==1) return nums;
        deque<int> window(nums.begin(),nums.begin()+k);//maintain a deque with size of k
        //找到Max第一个值
        int max0 = findmax(window);
        ans.push_back(max0);
        int i = k;
        while(i<nums.size()){
            int a = window.front();//将要弹出的数
            window.pop_front();
            if(a!=ans.back()){//将要弹出的数不是上一次找到的最大的数
                int b = ans.back();
                if(b>=nums[i]) ans.push_back(b);
                else ans.push_back(nums[i]);
                window.push_back(nums[i]);
                i++;
            }
            else{
                if(a<=nums[i]){
                    ans.push_back(nums[i]);
                    window.push_back(nums[i++]);
                } 
                else{
                    window.push_back(nums[i++]);
                    ans.push_back(findmax(window));
                } 
            }
        }
        return ans;
    }
    
    int findmax(deque<int> w){
        int max = w[0];
        for(int i=1; i<w.size();i++){
            if(max<w[i]) max = w[i];
        }
        return max;
    }
};
           

方法二：monoqueue

class Solution {//相当于维护一个Monoqueue
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        for (int i=0; i<nums.size(); i++) {
			if (!dq.empty() && dq.front() == i-k) dq.pop_front();
            while (!dq.empty() && nums[dq.back()] < nums[i])
                dq.pop_back();
            dq.push_back(i);
            if (i>=k-1) ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};
           

方法三：显示的monoqueue

class Monoqueue
{
    deque<pair<int, int>> m_deque; //pair.first: the actual value, 
                                   //pair.second: how many elements were deleted between it and the one before it.
    public:
        void push(int val)
        {
            int count = 0;
            while(!m_deque.empty() && m_deque.back().first < val)
            {
                count += m_deque.back().second + 1;
                m_deque.pop_back();
            }
            m_deque.emplace_back(val, count);
        };
        int max()
        {
            return m_deque.front().first;
        }
        void pop ()
        {
            if (m_deque.front().second > 0)
            {
                m_deque.front().second --;
                return;
            }
            m_deque.pop_front();
        }
};
struct Solution {
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> results;
        Monoqueue mq;
        k = min(k, (int)nums.size());
        int i = 0;
        for (;i < k - 1; ++i) //push first k - 1 numbers;
        {
            mq.push(nums[i]);
        }
        for (; i < nums.size(); ++i)
        {
            mq.push(nums[i]);            // push a new element to queue;
            results.push_back(mq.max()); // report the current max in queue;
            mq.pop();                    // pop first element in queue;
        }
        return results;
    }
};