IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> LeetCode每日一题-滑动窗口最大值 -> 正文阅读

[数据结构与算法]LeetCode每日一题-滑动窗口最大值

题目

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

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3

输出:[3,3,5,5,6,7]

分析

这道题先用暴力求解演练一遍对解题是有帮助的,因为它并没其它奇思妙想,都是在暴力法上加速。

先过一遍暴力法的过程:窗口每向前滑动一格,剔除最左边元素后再求窗口内最大值,过程非常简单。

暴力法时间复杂度为O(k*n),原因在于在每个窗口内找出最大值,每次都需要比较K次,加速的目标就在这。

问题核心其实就是求出动态数组最大值,如果将数组变成一个单向队列,可以将比较次数从K次减为1次,但维护有序数组每次插入新元素还是需要可能比较K次,这个时候可以通过删除可以被淘汰的数据来减少比较。

使用双端队列更方便淘汰元素,队列内维护不多于窗口大小的元素,队首是最大元素,并且始终保持从大到小的顺序,为了达到这个目的,每次加元素入队尾前,将比它小的元素淘汰,这样队列只保存了有意义数据,同时只保存元素下标会更方便淘汰窗口外的数据.

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<Integer>();
        int size = nums.length -k  >= 0 ?  nums.length - k + 1 : 1;
        int[] result = new int[size];
        for(int i=0;i<nums.length;i++){
           while(deque.size()>0 && nums[deque.peekLast()] <= nums[i]){
               deque.pollLast();
           }
            deque.addLast(i);
            if(i - deque.peekFirst() >= k){
                deque.pollFirst();
            }
            int index = i-k+1>=0? i-k+1:0;
            result[index] = nums[deque.peekFirst()];
        }
        return result;
    }
}

结果

关注个人微信公众号:肌肉码农,回复“好友”讨论问题。

?

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-26 12:18:24  更:2021-07-26 12:20:39 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/28 19:57:02-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码