239. Sliding Window Maximum

• Total Accepted: 49842
• Total Submissions: 157784
• Difficulty: Hard
• Contributors: Admin 

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.

Follow up:

Could you solve it in linear time?

Solution: (deque)

 

大概思路是用双向队列保存数字的下标，遍历整个数组，如果此时队列的首元素是i - k的话，表示此时窗口向右移了一步，则移除队首元素。然后比较队尾元素和将要进来的值，如果小的话就都移除，然后此时我们把队首元素加入结果中即可

1 class Solution { 2 public: 3     vector
          
            maxSlidingWindow(vector
           
            & nums, int k) { 4         vector
            
              res; 5         deque
             
               q; 6         for(int i = 0; i < nums.size(); i++){ 7             if(!q.empty() && q.front() == i - k) q.pop_front(); 8             while(!q.empty() && nums[q.back()] < nums[i]) q.pop_back();//while!!!! 只保留windows里面最大的在队首 9             q.push_back(i);//deque save the index10             if(i >= k - 1) res.push_back(nums[q.front()]);11         }12         return res;13     }14 };