239. 滑动窗口最大值

239. 滑动窗口最大值

思路：
1.暴力法，双层便利

java代码：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] results = new int[nums.length-k+1];

        for(int ri=k-1;ri<nums.length;ri++){
            int m = nums[ri];
            for(int li=ri-k+1;li<ri;li++){
                m = Math.max(m,nums[li]);
            }
            results[ri-k+1]=m;
        }
        return results;
    }
}

2.双端队列
维护一个双端队列deque 和一个数组result
从i开始遍历nums
把nums[i]的下标添加进队列尾部（添加时，按照nums[i]从大到小添加，如果加入的前面有比nums[i]小的，出队列）
例子：[8,3,4],5 ->[8,5]

w = i-k+1;
当w>=0时，开始判断deque的头部index是否<w，小于出队列，然后把deque的头部nums[i]添加进result

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] results = new int[nums.length-k+1];
        LinkedList<Integer> linkl = new LinkedList<Integer>();
    
        for(int i = 0;i<nums.length;i++){
            while(!linkl.isEmpty() && nums[linkl.peekLast()]<=nums[i]){
                //
                linkl.pollLast();
            }
            linkl.addLast(i);
            if(linkl.peek()<i-k+1){
                linkl.poll();
            }
            if(i>=k-1){
                results[i-k+1]=nums[linkl.peek()];
            }
        }

        return results;
    }
}      

3.动态规划

4.妖法