239. Sliding Window Maximum

First of all, I tried to use priority_queue (i.e. heap) to solve the problem. The idea is that the priority queue maintains the valid maximum number in the window. Then the question will be when the maximum number is not valid? There will be two cases. One is the top of heap is less than the new number. The other is the top of heap is out of the window. So we need to keep two information in one heap node, i.e. number and its index (Well index should be sufficient as number can be identified by index). The heap should be sorted by the number value. Also, once we meet an invalid heap top, we need to keep popping out invalid top until we have one or the heap becomes empty. Then we can push the new number into heap. What if we see the heap top is valid? We just need to push the new number into heap because we'll deal with all invalid numbers later when we encounter an invalid heap top. With regard to the result, we just need to push the heap top to the result. The running time is O(NlogN).

1:  class Solution {  
2:  public:  
3:    vector<int> maxSlidingWindow(vector<int>& nums, int k) {  
4:      priority_queue<pair<int, int>> heap;  
5:      vector<int> res;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        if (i < k) heap.push(make_pair(nums[i], i));  
8:        else {  
9:          while (!heap.empty() && (heap.top().first < nums[i] || i - heap.top().second >= k)) heap.pop();  
10:          heap.push(make_pair(nums[i], i));  
11:        }  
12:        if (i >= k-1) {  
13:          res.push_back(heap.top().first);  
14:        }  
15:      }  
16:      return res;  
17:    }  
18:  };  

There is O(n) solution. This solution uses double linked queue. Similar idea as before, the queue's front always keep the index of valid maximum number in the window. So when the front's index is out of the window, we remove the front. And then we check the back of the queue. Since we just need to keep the possible maximum number in the queue, we can remove all the numbers less than the new number. This is the same idea as line 8 and 9 in solution above. Since all the numbers are only processed twice, the running time is O(2N). Such double linked queue is also called monotonic queue.

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