LeetCode：239.滑动窗口最大值

解法一：暴力解法，每次窗口滑动，遍历窗口内的最大值是什么，记录下来，时间复杂度O(k*n)

解法二：使用双端队列

具体思路是：每次窗口移动，将进入窗口的值放入一个双端队列末尾，放入之前把双端队列中小于改值的元素移出，因为这个新放入的值一定是在这些值中最晚移出的，所以比他小的值存放在队列中已经没有意义了。然后判断移出的值是否是队列第一个元素，如果是，需要移出队列第一个元素。具体代码如下：

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> max = new ArrayDeque<>();
    int n = nums.length;
    if (n == 0) {
        return nums;
    }
    int result[] = new int[n - k + 1];
    int index = 0;
    for (int i = 0; i < n; i++) {
    	
    	//开始移动窗口了
        if (i >= k) {
        	//移出的元素刚好是之前窗口的最大值，需要移出队列
            if (max.peekFirst() == nums[i - k]) {
                max.removeFirst();
            }
        }
        
        //进入窗口的元素，进入队列的时候要把比自己小的元素从队列中移除，然后再进入
        while (!max.isEmpty() && nums[i] > max.peekLast()) {
            max.removeLast();
        }
        max.addLast(nums[i]);
        
        //到了第一个窗口，可以记录最大值了，后续每遍历一次需要记录一次
        if (i >= k - 1) {
            result[index++] = max.peekFirst();
        }
    }
    return result;
}