leetcode Ch6-Data Structure

 1 class Solution {
 2 public:
 3     vector<int> maxSlidingWindow(vector<int> &nums, int k) {
 4         deque<int> dq;
 5         vector<int> res;
 6         for (int i = 0; i < nums.size(); i++) {
 7             if (!dq.empty() && dq.front() == i - k) {
 8                 dq.pop_front();    
 9             }
10             while (!dq.empty() && nums[dq.back()] < nums[i]) {    
11                 dq.pop_back();
12             }
13             dq.push_back(i);
14             if (i >= k - 1) {
15                 res.push_back(nums[dq.front()]);
16             }
17         }
18         return res;
19     }
20 };

View Code

需要用到单调队列，详细可参考此文。