112. 求每次滑动窗口中的最大值（考察队列）

用户11332765

发布于 2024-11-01 17:13:46

1590

文章被收录于专栏：编程编程

题目描述

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

返回滑动窗口中的最大值实例：

解题思路

先了解什么是滑动窗口：先按示例1的数组来，窗口长度是3，窗口是向右移动，相当于是从数组的下标从0开始递增。增到下标为2时，满足窗口长度（这时窗口就形成了），然后计算窗口里3个数据的最大值。得到最大值后，窗口再向右移到一格，再计算窗口里3个数据的最大值。直到数组的最后一个元素形成的窗口比较完成，滑动窗口结束。
对于求**的最大值，我们可优先考虑队列来做
创建个数组result 用来保存每个窗口的最大值
本题用双向队列来实现，使用LinkedList 存储数组的下标
定义一个变量：rightIndex，表示滑动窗口右边界
定义一个变量：leftIndex,表示滑动窗口左边界
遍历数组
- 用while循环，当队列非空时，数组滑动新的元素大于等于队尾的元素，则队尾的元素移掉，因为不是最大值；while循环结果条件，队列空了，或者数组滑动新的元素小于队尾的元素
- 把数组滑动新的元素添加到LinkedList 中
- 计算窗口左侧边界leftIndex
- 队首的元素是整个窗口里最大的，但是当数组滑动时，队首的元素已经不在窗口内，就要移除掉
- 因为数组的下标是从0开始，只有窗口右边界的下标+1>=k的值时，才能比较取窗口的最大值（队首的元素）
- 把队首元素保存到result 中。
- 最后把结果输出即可。

代码详解

package question;

import java.util.LinkedList;

/**
 * @author keke
 * @version 1.0
 * @className Question112
 * @description
 * @time 2022/8/20 22:20
 */
public class Question112 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] maxs = maxSlidingWindow(nums, k);
        for (int max : maxs) {
            System.out.println(max);
        }
    }

    private static int[] maxSlidingWindow(int[] nums, int k) {
        // 用来保存每个窗口的最大值
        int[] result = new int[nums.length - k + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        // 下标从0开始，遍历数组，rightIndex 表示滑动窗口右边界
        for (int rightIndex = 0; rightIndex < nums.length; rightIndex++) {
            // 用 while 循环，当队列非空时，数组滑动新的元素大于等于队尾的元素，则队尾的元素移掉，因为不是最大值
            // while 循环结果添加，队列空了，或者数组滑动新的元素小于队尾的元素
            while (!queue.isEmpty() && nums[rightIndex] >= nums[queue.peekLast()]){
                queue.removeLast();
            }
            // 存储数组右滑的下标
            queue.addLast(rightIndex);
            // 计算窗口左侧边界
            int leftIndex = rightIndex - k + 1;
            // 队首的元素是整个窗口里最大的，但是当数组滑动是，队首的元素已经不在窗口内，就要移除掉
            if (queue.peekFirst() < leftIndex){
                queue.removeFirst();
            }
            // 因为数组的下标是从0开始，只有窗口右边界的下标+1>=k的值时，才能比较取窗口的最大值（队首的元素）
            if (rightIndex + 1 >= k){
                result[leftIndex] = nums[queue.peekFirst()];
            }
        }
        return result;
    }
}