数据结构与算法-算法-239. 滑动窗口最大值

题目：

239. 滑动窗口最大值 - 力扣（LeetCode）239. 滑动窗口最大值 - 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。 示例 1：输入：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示例 2：输入：nums = [1], k = 1输出：[1] 提示： * 1 <= nums.length <= 105 * -104 <= nums[i] <= 104 * 1 <= k <= nums.lengthhttps://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked

总结：

总体还是有难度的。毕竟是滑动窗口，就要维护一个窗口正常。当窗口第一次正常的时候就要开始放值。

同时，利用双端队列维护一个单调性，保证左边都是最大值就行。

代码示例：

 

    /**
     * 滑动窗口最大值算法
     * @param nums 输入数组
     * @param k 滑动窗口大小
     * @return 每个滑动窗口的最大值数组
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        // 使用双端队列存储数组索引，维护单调递减性质
        // 队列头部始终是当前窗口的最大值索引
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int let = nums.length;
        int[] ans = new int[let -k +1];
        for (int i = 0; i < let; i++) {

            //第一个循环,维护窗口，抛弃左边的值
            // 如果队列头部的索引小于窗口左边界，说明已经不在当前窗口内了
            while(!deque.isEmpty() && deque.peekFirst() < i-k+1){
                deque.removeFirst();
            }
            //第二个循环，维护单调性
            // 因为这些较小的元素永远不可能成为窗口最大值（当前元素更大且更新）
            while(!deque.isEmpty() &&
            nums[i] > nums[deque.peekLast()] // 新值 nums[i] 》 最右边的值。表明当前最右边的值没用，
            ){
                deque.removeLast();
            }
            deque.addLast(i);

            //保证窗口完整，窗口第一次完整就要放值
            if( i-k +1 >= 0){//
                ans[i-k+1] = nums[deque.peekFirst()];
            }
        }
        return ans;
    }