首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >112. 求每次滑动窗口中的最大值(考察队列)

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

作者头像
用户11332765
发布于 2024-11-01 09:13:46
发布于 2024-11-01 09:13:46
11400
代码可运行
举报
文章被收录于专栏:编程编程
运行总次数:0
代码可运行

题目描述

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

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

解题思路

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

代码详解

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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;
    }
}

运行截图

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-08-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
leetcode刷题(43)——239. 滑动窗口最大值
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
老马的编程之旅
2022/06/22
2670
【腾讯云Cloud Studio实战训练营】Cloud Studio 快速搭建学习分享
最近接触到了一款开发神器,云端IDE,相比于传统的 IDE,云端 IDE 可以更大程度的提升用户工作的效率。
用户10671819
2023/07/31
3780
【腾讯云Cloud Studio实战训练营】Cloud Studio 快速搭建学习分享
滑动窗口最大值
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
opencode
2022/12/26
1.4K0
滑动窗口最大值
算法刷题(2):返回滑动窗口最大值
题目:Sliding Window MaximumGiven 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 knumbers in the window. Each time the sliding window moves right by one position. Retu
xujjj
2019/07/16
6230
LeetCode239. 滑动窗口最大值
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
静谧星空TEL
2021/04/27
5110
滑动窗口最大值:单调队列
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
利刃大大
2023/04/12
5740
滑动窗口最大值:单调队列
滑动窗口最大值(LeetCode 239)
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
恋喵大鲤鱼
2023/12/18
2120
滑动窗口最大值(LeetCode 239)
使用单调队列解决 “滑动窗口最大值” 问题
在上一篇文章中[2],我们介绍了单调栈这种特殊的栈结构,单调栈是一种非常适合处理 “下一个更大元素问题” 的数据结构。今天,分享到单调栈的孪生兄弟 —— 单调队列(Monotonic Queue)。类似地,单调队列也是在队列的基础上增加了单调的性质(单调递增或单调递减)。那么单调队列是用来解决什么问题的呢?
用户9995743
2022/12/22
1.2K0
使用单调队列解决 “滑动窗口最大值” 问题
LeetCode每日一题-2:滑动窗口的最大值
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释:
墨明棋妙27
2022/09/23
1790
golang刷leetcode 滑动窗口(8)滑动窗口最大值
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
golangLeetcode
2022/08/02
5460
滑动窗口最大值(239)题解 难度:困难
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
余生大大
2022/11/02
2960
滑动窗口最大值(239)题解 难度:困难
如何取滑动窗口中的最大值
这道题需要保存一个值的集合,因为随着滑动窗口的移动,最大值会被移除窗口,次大值会变成最大值;为了方便最大值的比较,最好是个有序的集合.
一个架构师
2022/06/20
2K0
如何取滑动窗口中的最大值
日拱算法,滑动窗口的最大值
携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第30天,点击查看活动详情
掘金安东尼
2022/09/22
3980
日拱算法,滑动窗口的最大值
滑动窗口最大值引出一个重要数据结构
https://leetcode-cn.com/problems/sliding-window-maximum/
代码随想录
2021/07/16
5840
Java双端队列给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。
双端队列实现 给定一个数组 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
编程张无忌
2021/01/26
1.3K0
刷题日常(找到字符串中所有字母异位词,​ 和为 K 的子数组​,​ 滑动窗口最大值​,全排列)
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
用户11369558
2024/12/24
1870
刷题日常(找到字符串中所有字母异位词,​ 和为 K 的子数组​,​ 滑动窗口最大值​,全排列)
辛辣天塞!滑动窗口之【和的最大值】&amp;【最大值集合】
噢!用 Math.max() 来每次从窗口找最大值,时间复杂度是 O(n * k),仍然很大;
掘金安东尼
2022/09/19
5090
辛辣天塞!滑动窗口之【和的最大值】&amp;【最大值集合】
滑动窗口最大值问题
思路:滑动窗口,在数组位置建立一个双端队列利用出入队列来模拟窗口平移,即首先把第一个窗口入进去,接着i遍历原数组剩下的元素,每次入剩下的元素相当于窗口右移,对于维护窗口即维护队列,由于要的是每次得到的窗口中最大值故当每次入队列的时候,比较原值和队列放的队尾下标对应的值,如果原值大即right--,把它往队前放,反之放后面 目的:(每次队列中放入的是原数组下标,这样操作为了保证队列中的下标是升序,对应的值为降序,每次取窗口的最大值,即left处值)(可能队列中数据不足k个但由于每次只要最大值,即left处,可以控制当每次新入数据,通过维护队列,使得left处为最大值,只要保证每次队列数据<=k即可)。
羑悻的小杀马特.
2025/01/23
1360
滑动窗口最大值问题
LeetCode 239. 滑动窗口最大值(双端队列+单调栈)
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
Michael阿明
2021/02/20
5190
LeetCode 239. 滑动窗口最大值(双端队列+单调栈)
滑动窗口求最大值 leetcode 59
滑动窗口最大值问题 利用递减队列实现 Dequeue dequeue = new LinkedList<>(); 递减队列方法说明 peekFirst获取队头元素 pollFirsr队头元素出队 offerLast == add在队尾插入新元素
全栈程序员站长
2022/09/14
3040
推荐阅读
相关推荐
leetcode刷题(43)——239. 滑动窗口最大值
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档