• 算法通关村16关 | 堆与滑动窗口问题结合


    1. 堆与滑动窗口问题结合

    题目

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

    思路

    对于最大值、k个最大值这种场景,优先队列(堆)是首先应该考虑的思路。大根堆可以帮我们实时维护一系列中的最大值。

            把nums中前k个元素放入队中,作为初始值,第一个最大值就可以知道了,每次向右移动滑动窗口的时候,我们可以取出其中的最大值,当然最大值不一定在滑动窗口中的第一个元素,(如图中第6行第7行)因为窗口的大小固定,所以最多k-1次移动取出最大值,最少直接在首位取出,所以堆的大小其实是固定的,并不会太大,因为我们需要知道堆中元素在数组中的索引位置,索引存储二元数组(num,index)

    整个过程大概就是边向右滑动边取出最大值的过程,当pq.peek()[1] <= i - k的时候,最大的元素是在窗口左端的左侧,在窗口外面,需要删除。

    代码

    1. public int[] maxSlidingWindow(int[] nums, int k){
    2. int n = nums.length;
    3. PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
    4. @Override
    5. public int compare(int[] o1, int[] o2) {
    6. //正数单调递减
    7. return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1];
    8. }
    9. });
    10. for (int i = 0; i < k; i++) {
    11. pq.offer(new int[]{nums[i],i});
    12. }
    13. int[] ans = new int[n - k + 1];
    14. //第一个最大值
    15. ans[0] = pq.peek()[0];
    16. for (int i = k; i < n; i++) {
    17. pq.offer(new int[]{nums[i],i});
    18. //判断最大值是否是窗口的第一个元素,是第一个元素因为窗口需要向前滑动,窗口大小固定,所以窗口中第一个元素需要移除
    19. while (pq.peek()[1] <= i - k){
    20. pq.poll();
    21. }
    22. ans[i - k + 1] = pq.peek()[0];
    23. }
    24. return ans;
    25. }

  • 相关阅读:
    mongodb使用debezium
    苹果cms模板MXone V10.7魔改版源码 全开源
    从装饰模式和职责链模式看链式结构模式
    [Java框架] Java常用爬虫框架推荐
    实用的Visual Studio插件
    模板、外观、观察者、建造者
    EluxJS-让你像切蛋糕一样拆解前端巨石应用
    Linux的进程管理
    springcloud 整合 RabbitMQ 消息中间件
    通过shiro进行按钮及页面访问url的权限控制
  • 原文地址:https://blog.csdn.net/m0_54138535/article/details/132683518