devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录算法训练营第三期day13-栈与队列03_(pair1, pair2)->pair2[1]-pair1[1]

作者：小蓝xlanll | 2024-03-21 00:26:22

赞

踩

(pair1, pair2)->pair2[1]-pair1[1]

目录

1.T239：滑动窗口最大值

思路

代码实现

法1、自定义单调队列

法2、用元素索引代替元素

2.T347：前K个高频元素

代码实现

大顶堆

小顶堆

1.T239：滑动窗口最大值

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

返回 滑动窗口中的最大值 。

提示：

  • 1 <= nums.length <= 105

  • -104 <= nums[i] <= 104

  • 1 <= k <= nums.length

进阶：

你能在线性时间复杂度内解决此题吗？

S：

思路

个人认为本题应该是代码随想录刷题主线（不算“其他题目”）至今最难的一题

        如果考虑每次都怎么在滑动窗口中求局部最大值，那样时间复杂度绝对超出线性，目测O(n*k)起步

首先，可以明确的是：滑动窗口每次移动，都必定会有1个数进窗，有1个数出窗；

        从这一角度出发，我们能不能使用以栈或队列数据结构实现的容器，使得每次弹出的数都是局部最大值？

        很明显，没有现成的，但是可以自己实现！

代码实现

法1、自定义单调队列

  1. class MyQue {
  2.     private Deque<Integer> queue = new ArrayDeque<>();
  3.  
  4.     // 看一下当前要弹出的数值，是否等于队列出口元素的数值，相等才弹出
  5.     public void poll(int value) {
  6.         if (!queue.isEmpty() && queue.getFirst() == value) {
  7.             queue.poll();
  8.         }
  9.     }
  10.  
  11.     // 如果push的数值大于入口元素的数值，那么就将队列后端的数值一个一个地弹出，直到push的数值小于等于队列入口元素的数值
  12.     // 这样就保证了队列里的数值是（从队头到队尾）单调非递增的
  13.     public void add(int value) {
  14.         while (!queue.isEmpty() && value > queue.getLast()) {
  15.             queue.removeLast();
  16.             // queue.poll();
  17.         }
  18.         queue.add(value);//addLast
  19.     }
  20.         
  21.     // 查询当前队列里的最大值 直接返回队列前端也就是front就行
  22.     public int peek() {
  23.         return queue.getFirst();//等效于peek
  24.     }
  25. }
  26.  
  27. class Solution {
  28.     public int[] maxSlidingWindow(int[] nums, int k) {
  29.         if (nums == null || nums.length <= 1) return nums;
  30.         MyQue myque = new MyQue();
  31.         int[] res = new int[nums.length - k + 1];//数组的长度
  32.         // 先将前k的元素放进队列
  33.         for (int i = 0; i < k; ++i) {
  34.             myque.add(nums[i]);
  35.         }
  36.         int num = 0;
  37.         res[num++] = myque.peek();//漏了
  38.         for (int i = k; i < nums.length; ++i) {
  39.             myque.poll(nums[i - k]);// 滑动窗口移除最前面元素（当然不是一定会移除）
  40.             myque.add(nums[i]);
  41.             res[num++] = myque.peek();
  42.         }
  43.         return res;   
  44.     }
  45. }

法2、用元素索引代替元素

  1.     public int[] maxSlidingWindow(int[] nums, int k) {
  2.         ArrayDeque<Integer> deque = new ArrayDeque<>();
  3.         int n = nums.length;
  4.         int[] res = new int[n - k + 1];
  5.         int idx = 0;
  6.         for(int i = 0; i < n; i++) {
  7.             // 根据题意，i为nums下标，是要在窗口[i - k + 1, i]中选最大值，只要保证两点
  8.             // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
  9.             while(!deque.isEmpty() && deque.peek() < i - k + 1) {//
    声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/277078
    推荐阅读
    相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。