Leetcode 239 Sliding Window Maximum

思路一： brute force，直接上代码：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int count = nums.length - k + 1;
        int[] res = new int[count];
        for(int i = 0; i < count; i++){
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++){
                max = Math.max(max,nums[j]);
            }
            res[i] = max;
        }
        return res;
    }
}

思路二： 构建一个单调递减的deque，deque存放当前window的下标，这样deque的第一个元素就是当前window的答案。每次向右滑动的话，进行两个操作，remove last和（必要的话）remove first（因为deque的长度最长是k，但不一定会是k，可能小于k，小于的时候就不要remove first）。这两操作完了就在deque尾部加入下一个window的元素（addlast操作）。具体思路看下面这个链接：链接。下面直接上代码，代码上我也备注了很多注释：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        // deque用来存放当前window下标，deque里面存的是index，但是index对应的值是单调递减的，这样就能保证deque的first element是最大的，就是当前window的最大值，也就是我们需要的答案
        Deque<Integer> deq = new ArrayDeque<>();
        
        // ans用来存放答案
        int[] ans = new int[nums.length - k + 1];
        
        // i用来追踪当前window的最后一个数的下标
        for(int i = 0; i < nums.length; i++){
            
            // 这个循环用来去除不可能是答案的那些下标，因为马上要新进来的数是i，i是要放在deque最末的，也就是要最小的，那么当前deque中比i小的都要去除，这样才能保证i加进去后是最小的
            while(!deq.isEmpty() && nums[i] > nums[deq.getLast()]){
                deq.removeLast();
            }
            
            // 因为上面removelast操作，所以导致deque长度可能是小于k的（去掉的那些都是不可能成为答案的数）。但deque最长的时候也可能是k，所以当deque长度为k时，这时候i要加进来，那么就必须把deque中的第一个element给删了，才能在尾巴加上i。除此之外，不用remove first
            if(!deq.isEmpty() && deq.getFirst() == i - k){
                deq.removeFirst();
            }
            
            // 在尾部加入新元素，此时i是最小的
            deq.addLast(i);
            
            // 只有当i至少走过k个元素后（产生第一个window），才会产出答案
            if(i - k + 1 >= 0){
                ans[i - k + 1] = nums[deq.getFirst()];
            }
        }
        return ans;
    }
}

总结：

1. 碰到这种持续求最大最小值的题目可以考虑priority queue（heap），stack，deque之类的数据结构
2. 这题我没有借此机会好好了解deque数据结构，只了解到可以双向插入数据，具体一些性质以及方法，复盘的时候要好好理解归纳。