Description:
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.
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?
Example:
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].
Link:
https://leetcode.com/problems/sliding-window-maximum/description/
解題方法：
如果我們能有一個維持descending的結(jié)構(gòu)儲存window里面的數(shù)字痕支，那么這個問題就很容易解決沿侈。
max heap可以滿足我們的需求亿驾，但是每次刪除數(shù)字會額外耗費時間漩绵。
雙向隊列可以滿足線性的要求，我們可以手動維護隊列的順序逗扒，當(dāng)隊尾的元素小于新來的元素都哭，就pop_back，隊頭的元素維持當(dāng)前窗口最大延欠，當(dāng)隊頭的元素不在窗口范圍內(nèi)，就pop_front沈跨。
為什么當(dāng)隊尾的元素小于最先來的元素可以直接pop而不是存下來接著排序呢由捎？
因為我們已經(jīng)有了比他們還要大的，新的元素到來饿凛，當(dāng)這個新的元素沒有過期時（在窗口范圍內(nèi)）狞玛，那些需要pop的元素永遠不可能成為最大的元素邻奠。當(dāng)這個新的元素過期時，那些需要pop的元素都肯定過期为居。所以我們可以直接pop掉不用保留下來碌宴。
Tips:
Time Complexity：
O(N)
完整代碼：
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> Q;
for(int i = 0; i < nums.size(); i++) {
while(!Q.empty() && i - k >= Q.front())
Q.pop_front();
while(!Q.empty() && nums[i] > nums[Q.back()])
Q.pop_back();
Q.push_back(i);
if(i >= k - 1)
result.push_back(nums[Q.front()]);
}
return result;
}
