Amazon-Sliding Window Maximum (H

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[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

Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Solution:

public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null||nums.length==0||k>nums.length||k<1) return new int[0];
        
        int[] res=new int[nums.length-k+1];
        LinkedList<Integer> max=new LinkedList<>();

        int resIndex=0;
        for(int i=0;i<nums.length;i++){
            while(max.size()>0 && max.peekFirst()<i-k+1){
                max.pollFirst();
            }
            
            while(max.size()>0 && nums[max.peekLast()]<nums[i]){
                max.pollLast();
            }
            
            max.offerLast(i);
            
            if(i>=k-1){
                res[resIndex++]=nums[max.peekFirst()];
            }
        }
        
        return res;

时间复杂度：O(n)
空间复杂度：O(k)

一开始我的思路就是暴力的解法，每个窗口都遍历一次，时间复杂度是O(n*k)，空间复杂度是O(1)，倒是通过了题目。但是进一步要求O(n)，打算用队列但是没什么思路。写不出来就只能理解别人写的代码，然后记住这个思路：第一步，每次遍历开始检查窗口是否合法，也就是双端队列max是否超过窗口大小（这里的max队列存储的数组的索引，也就是说队头索引小于当前位置-k+1的时候，说明窗口已经滑过它，此时应出队）。第二步，是判断max队列里队尾索引指向的元素是否小于该位置i（从队尾比较是因为每次窗口都会出队队头索引，可以理解为队尾是该位置i之前的索引，如果小于位置i的值，那么早晚也是要出队的，不如直接出队，留下队头元素指向当前窗口最大的索引，如果不小于，那么说明max队列内索引的值是降序的）。第三步，队尾加入索引i，表明窗口右端到达该位置。第四步，如果i已经划到k-1的位置了，说明窗口已经正式开始滑动了，此时max队列队头索引的值就是当前窗口的最大值，记录在结果数组中。

模拟一次就知道了
nums : 1,3,-1,-3,5,3,6,7
max                        res
---------------            -----
1
3
3 -1                         3
3 -1 -3                      3
5                            5
5  3                         5
6                            6
7                            7

这个方法我一开始认为是O(n*k)的，之后发现最多入队n个元素，最多出队n-1个元素，实际上是线性的，且查找队头，队尾，插入、删除队头队尾都是O(1)，确实是妙啊！
另外题目里只是说了k在nums不为空的时候合规，所以还是要判断一下输入参数是否合法的，本题不合法的情况返回一个零长数组而不是null。