LeetCode 239-滑动窗口最大值

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

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

示例:

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

输出: [3,3,5,5,6,7]

这道题两种思路，第一种思路就是暴力法，一开始截取数组中k个数，循环计算最大值，依次类推。这种办法的复杂度是N的平方，而且空间复杂度也比较高。

这种办法肯定不是面试官想要听的，因此就要使用其他一种办法。

思路就是，先申明一个queue，循环输入，每输入一个，就判断跟前面的比是不是最大的，如果不是，就插入到后面，如果是，就把前面的删除。然后数据输入达到k个值，就开始加queue中的第一个数据到结果中。

实际实现时，注意下面两点：

(1)每次在队列末尾插入数据时，保证前面的数都要比它大，否则将前面的数都删除。

(2)在window中应该记录数据的下标，而不是数据的实际值，否则在清理过期数据时，会判断不出来是否该把头元素删除。

代码：

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(null == nums || nums.length == 0 || k==0){
            return new int[0];
        }

        Queue<Integer> window = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();

        for(int i=0;i<nums.length;i++){
            if (i>=k&&window.peek()<=i-k){
                window.poll();
            }
            while (window.size()!=0 && nums[((ArrayDeque<Integer>) window).peekLast()] <= nums[i]){
                ((ArrayDeque<Integer>) window).pollLast();
            }
            window.add(i);
            if (i>=k-1){
                res.add(nums[window.peek()]);
            }
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }