Java 滑动窗口最大值的实现

作者:南淮北安 时间:2021-09-10 15:34:20 

一、题目

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

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

Java 滑动窗口最大值的实现

二、单调队列解析

题目让求随着滑动窗口的滑动,返回窗口覆盖范围的最大值

该题不适合优先级队列,因为采用大顶堆存放k个数字,可以知道此时的最大值,但是窗口是滑动的,大顶堆每次只能弹出最大值,无法移除其他值,即无法用大顶堆维护滑动窗口里的值。

所以采用队列维护,随着窗口的移动,队列先进先出

此时对队列的要求是,队列首位为最大值,整个队列呈递减
例如:1,3,-1,-3,5,3,6,7

初始:1,3,-1,队列存入3,-1,使其保持递减,且首位为此时滑动窗口的最大值
移动到-3,队列:3,-1,-3
移动到5,队列:5
移动到3,队列:5,3
移动到6,队列:6
移动到7,队列:7

所以为了满足要求,需要自定义队列

从示例可以看出,队列没必要维护窗口里所有元素,只需要保证队列首位此时窗口的最大,而且,队列元素为递减,具体看代码

三、代码


import java.util.Deque;
import java.util.LinkedList;
//自定义数组
class MyQueue {
   Deque<Integer> deque = new LinkedList<>();
   //弹出元素时,比较当前要弹出的数值是否等于队列出口的数值,如果相等则弹出
   //同时判断队列当前是否为空
   void poll(int val) {
       if (!deque.isEmpty() && val == deque.peek()) {
           deque.poll();
       }
   }
   //添加元素时,如果要添加的元素大于入口处的元素,就将入口元素弹出
   //保证队列元素单调递减
   //比如此时队列元素3,1,2将要入队,比1大,所以1弹出,此时队列:3,2
   void add(int val) {
       while (!deque.isEmpty() && val > deque.getLast()) {
           deque.removeLast();
       }
       deque.add(val);
   }
   //队列队顶元素始终为最大值
   int peek() {
       return deque.peek();
   }
}

class Solution {
   public int[] maxSlidingWindow(int[] nums, int k) {
       if (nums.length == 1) {
           return nums;
       }
       int len = nums.length - k + 1;
       //存放结果元素的数组
       int[] res = new int[len];
       int num = 0;
       //自定义队列
       MyQueue myQueue = new MyQueue();
       //先将前k的元素放入队列
       for (int i = 0; i < k; i++) {
           myQueue.add(nums[i]);
       }
       res[num++] = myQueue.peek();
       for (int i = k; i < nums.length; i++) {
           //滑动窗口移除最前面的元素,移除是判断该元素是否放入队列
           myQueue.poll(nums[i - k]);
           //滑动窗口加入最后面的元素
           myQueue.add(nums[i]);
           //记录对应的最大值
           res[num++] = myQueue.peek();
       }
       return res;
   }
}

四、总结

该题利用了单调队列,需要自己定义入队出队规则

入队:保持队首元素始终最大,同时队内维护窗口的大小个元素,呈现递减

出队:判断当前元素是否入队,在队内,再随着窗口的滑动执行出队操作

来源:https://blog.csdn.net/nanhuaibeian/article/details/117047732

标签:Java,滑动窗口最大值
0
投稿

猜你喜欢

  • 一文了解Java读写锁ReentrantReadWriteLock的使用

    2023-10-12 19:28:21
  • Freemarker如何生成树形导航菜单(递归)

    2023-02-24 13:52:16
  • 通过springboot+mybatis+druid配置动态数据源

    2023-06-20 16:48:30
  • Android编程之selector下设置背景属性值的方法

    2023-08-23 08:07:49
  • java微信企业号开发之通讯录

    2022-04-28 12:51:40
  • SpringBoot2.6.x升级后循环依赖及Swagger无法使用问题

    2021-12-02 09:49:43
  • 解决response.setHeader设置下载文件名无效的问题

    2021-08-15 20:43:54
  • 浅谈十个常见的Java异常出现原因

    2022-10-04 07:58:50
  • Android 自定义输入支付密码的软键盘实例代码

    2021-08-09 11:41:43
  • SpringBoot整合java诊断工具Arthas解读

    2023-08-07 10:39:03
  • c# chart缩放,局部放大问题

    2021-09-26 20:46:40
  • Spring实例化bean的四种方式详解

    2022-01-19 23:09:15
  • C#几种截取字符串的方法小结

    2023-07-16 09:55:10
  • 使用Java读取Word文件的简单例子分享

    2022-12-17 02:15:19
  • java split用法详解及实例代码

    2022-06-27 06:48:19
  • protobuf与json转换小结

    2023-01-23 15:26:34
  • Java线程同步机制_动力节点Java学院整理

    2023-08-01 10:29:47
  • Flutter利用注解生成可自定义的路由的实现

    2022-08-28 15:12:16
  • java swing标准对话框具体实现

    2021-12-30 02:48:50
  • Java关键字finally_动力节点Java学院整理

    2022-09-25 11:15:30
  • asp之家 软件编程 m.aspxhome.com