题目
答案
最直观的解法应该是用一个heap来存储当前window的内容，当slide到下一个window时，获取heap中maximum元素。这个解法有一个不方便之处，就是java和c++的heap都不支持sliding window所需要的删除任意元素这个操作(如果你自己实现heap就另当别论)
在这种情况下可以采用lazy delete的策略，在取maximum时，如果发现该元素不在当前window，则直接丢弃，继续取到合法的maximum为止。
此算法复杂度为O(nlogk)
第二个解法使用deque数据结构，详细原理可看以下文章
https://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html
算法复杂度为O(n)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0) return new int[]{};
// deque is a window of at most size k that ends at index i
Deque<int[]> dq = new ArrayDeque<>();
int[] ret = new int[nums.length - k + 1];
for(int i = 0; i < nums.length; i++) {
// This keeps the deque a decreasing sequence
while(!dq.isEmpty() && dq.getLast()[1] <= nums[i])
dq.removeLast();
// Add new element to deque
dq.offerLast(new int[]{i, nums[i]});
// Kick out elements that are not no longer in the window
if(!dq.isEmpty() && dq.getFirst()[0] <= i - k)
dq.removeFirst();
// pick the first one in the window
if(i >= k - 1) ret[i - k + 1] = dq.getFirst()[1];
}
return ret;
}
}
