239. 滑动窗口最大值(一般)

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置                最大值

---------------               -----

[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

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum

思路1:(作为2的补充理解)

遍历数组，将数存放在双向队列中，并用L,R来标记窗口的左边界和右边界。队列中保存的并不是真的数，而是该数值对应的数组下标位置，并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大，则需要弹出队尾值，直到队列重新满足从大到小的要求。刚开始遍历时，L和R都为0，有一个形成窗口的过程，此过程没有最大值，L不动，R向右移。当窗口大小形成时，L和R一起向右移，每次移动时，判断队首的值的数组下标是否在[L,R]中，如果不在则需要弹出队首的值，当前窗口的最大值即为队首的数。

示例
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

解释过程中队列中都是具体的值，方便理解，具体见代码。（最大值永远都是左边的元素）
初始状态：L=R=0,队列:{}
i=0,nums[0]=1。队列为空,直接加入。队列：{1}
i=1,nums[1]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：{3}
i=2,nums[2]=-1。队尾值为3，-1<3，直接加入。队列：{3,-1}。此时窗口已经形成，L=0,R=2，result=[3]
i=3,nums[3]=-3。队尾值为-1，-3<-1，直接加入。队列：{3,-1,-3}。队首3对应的下标为1，L=1,R=3，有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3，5>-3，依次弹出后加入。队列：{5}。此时L=2,R=4，有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5，3<5，直接加入。队列：{5,3}。此时L=3,R=5，有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3，6>3，依次弹出后加入。队列：{6}。此时L=4,R=6，有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6，7>6，弹出队尾值后加入。队列：{7}。此时L=5,R=7，有效。result=[3,3,5,5,6,7]

通过示例发现R=i，L=k-R。由于队列中的值是从大到小排序的，所以每次窗口变动时，只需要判断队首的值是否还在窗口中就行了。
解释一下为什么队列中要存放数组下标的值而不是直接存储数值，因为要判断队首的值是否在窗口范围内，由数组下标取值很方便，而由值取数组下标不是很方便。

作者：hanyuhuang
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/

思路2：

思路：滑动窗口应当是队列，但为了得到滑动窗口的最大值，队列序可以从两端删除元素，因此使用双端队列。队列第一个位置保存当前窗口的最大值。
- 注意队列存的是最大值下标
- 原则：对新来的元素k，将其与双端队列中的元素相比较
  
  1）前面比k小的，直接移出队列（因为不再可能成为后面滑动窗口的最大值）
  
  2）前面比k大的X，比较两者下标，判断X是否已不在窗口之内，不在了，直接移出队列

最标准的解法，因为k固定，且不用维护第二大第三大的值

回看记录200525

又看了一遍，滑动窗口，，用优先队列可以了解，但是双向队列的方法存储下标，不是很好能够了解关系，有点绕。

代码1：

//这里是双向队列的解法，仅维护最大值即可O(n)
class Solution {
    public int[] maxSlidingWindow(final int[] nums, final int k) {
        if(nums == null || nums.length<=1)
            return nums;//只有一个元素或者空，直接返回就行
        final LinkedList<Integer> queue = new LinkedList<Integer>();//queue存下标而非真实值，为了方便判断队首的值是否在窗口范围内
        //结果数组，比原来的数少k-1个
        final int[] res = new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            //保证从小到大，如果前面数小则依次弹出，直到满足要求
            //保证左边元素最大
            while(!queue.isEmpty() && nums[queue.peekLast()]<=nums[i])
                queue.pollLast();

            //这里是添加,存下标，而非值
            queue.addLast(i);
            //判断当前队列中队首的值是否有效即判断当前最大值的下标是否越界，这句不是很好理解啊
            if(queue.peek()<=i-k)
                queue.poll();
            //当窗口大小为k时，向result数组中添加最大元素
            if(i>=k-1)
                res[i-k+1] = nums[queue.peek()];
        }
        return res;
    }
}

代码2：

/**
  * 使用大根堆，但是大根堆每次移除元素时间复杂度O(k)，取堆顶O(1)，总体时间复杂度高，为O(N*logk)
*/
 public ArrayList<Integer> maxInWindows2(int[] num, int size) {
 	if (num == null || num.length == 0 || size <= 0 || num.length < size) {
        return new ArrayList<>();
    }
    ArrayList<Integer> result = new ArrayList<>();
    PriorityQueue<Integer> q = new PriorityQueue(size, Comparator.reverseOrder());
    for (int i = 0; i < num.length; i++) {
        if (q.size() == size) {
           q.remove(num[i - size]);
        }
        q.add(num[i]);
        if (i >= size - 1) {
           result.add(q.peek());
         }
     }
     //int[] arr = new int[result.size()];
     //for (int i = 0; i < result.size(); i++) {
     //   arr[i] = result.get(i);
     //}
     //return arr;
     return result;
}

作者：icecrea
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-liang-chong-fang-fa-qiu-jie-da/