算法通关村 —— 滑动窗口与堆结合

这篇具有很好参考价值的文章主要介绍了算法通关村 —— 滑动窗口与堆结合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

堆与滑动窗口问题的结合

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

输入: nums = [1,3,-1,-3,5,3,6,71,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

这种方法在基础算法的堆部分出现过。对于最大值、K个最大这种场景优先队列 (堆)是首先应该考虑的思路。大根堆可以帮助我们实时维护一系列元素中的最大值。

本题初始时,我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时,我们就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中,在这种情况下,这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此,当我们后续继续向右移动窗口时,这个值就永远不可能出现在滑动窗口中了,我们可以将其永久地从优先队列中移除

我们不断地移除堆顶的元素直到其确实在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。

为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组(num,index),表示元素 num 在数组中的下标为 index。文章来源地址https://www.toymoban.com/news/detail-738627.html

public class MaxSlidingWindow {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 定义最大堆(优先队列),比较的是num值,num值相等再比较索引
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        // 先入堆k个
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1]; // 存储滑动窗口中的最大值
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            // 继续入堆
            pq.offer(new int[]{nums[i], i});
            // 如果最大值的索引不在滑动窗口内,则将其出堆,直到其在滑动窗口内
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            // 存储当前滑动窗口最大值
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
    // 测试
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(result));
    }

}

到了这里,关于算法通关村 —— 滑动窗口与堆结合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode算法小抄--滑动窗口算法

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计6244字,阅读大概需要3分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(38)
  • 【算法】基础算法002之滑动窗口(二)

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言  5.水果成篮(medium)  6.找到字符串中所有字母异位词 7.串联所有单词的

    2024年02月20日
    浏览(46)
  • 【算法】基础算法002之滑动窗口(一)

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.长度最小的子数组 滑动窗口类问题解题思路大纲: 2.无重复字符的最长

    2024年02月19日
    浏览(43)
  • 【算法优选】 滑动窗口专题——壹

    基本概念 滑动窗口是一种 基于双指针 的一种思想,两个指针指向的元素之间形成一个窗口。 分类:窗口有两类,一种是 固定大小类 的窗口,一类是 大小动态变化 的窗口。 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长

    2024年02月08日
    浏览(39)
  • 【算法|数组】滑动窗口

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 暴力解法 这种做法可以很容易想到,可是谁

    2024年02月12日
    浏览(39)
  • 算法专题整理:滑动窗口

    视频课程:同向双指针 滑动窗口【基础算法精讲 01】_哔哩哔哩_bilibili 滑动窗口也可以理解为双指针法的一种。 滑动窗口的核心在于 连续 !如果需要得到的结果是 满足某种较为明显条件 的 连续 的 子数组 ,可以考虑使用滑动窗口来做。 通常情况下,滑动窗口是 枚举右端

    2024年02月12日
    浏览(47)
  • 算法专题二:滑动窗口

    长度最小的子数组 思路一: 思路二: 无重复字符的最长子串 思路一: 最大连续1的个数 开头位0 并且k为0算是一个特殊的情况这样的情况有一些考虑就走不出去前面的0而忽略到后面数组自带1,走不到这些1数据导致记录连续1的个数出问题! 将x减小到0的最小操作数 水果成篮

    2024年02月02日
    浏览(47)
  • 算法——滑动窗口

    滑动窗口大致分为两类:一类是窗口长度固定的,即left和right可以一起移动;另一种是窗口的长度变化(例如前五道题),即right疯狂移动,left没怎么动,这类题需要观察单调性(即指针)等各方面因素综合思考 长度最小的子数组 子数组需要为连续的区间 需要在满足条件的前

    2024年04月10日
    浏览(36)
  • 【滑动窗口】算法实战

    滑动窗口 ,顾名思义,就是有一个大小可变的窗口,左右两端方向一致的向前滑动 ( 右端固定,左端滑动;左端固定,右端滑动 )。 滑动窗口的本质其实也是一种双指针算法,它是根据 单调性 的思想,使用” 同向双指针 “,索引字符串或者列表中的一个区间 [left,rig

    2024年02月15日
    浏览(34)
  • 【算法小课堂】滑动窗口

    滑动窗口本质是双指针算法的一种演变 本质上就是同向双指针,窗口的范围就是[left,right) 滑动窗口大致可以分为两类 窗口大小不变的 窗口大小变化的 滑动窗口遇到一些验证重复性的问题的时候可以用哈希表来优化 三步走: 窗口的形成初期 进窗口 开始遍历数组,right一直

    2024年02月07日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包