专栏首页mathorLeetCode239. 滑动窗口最大值

LeetCode239. 滑动窗口最大值

题目链接:LeetCode239

 暴力可以做,不知道能不能过,这题是一道双端队列求窗口最大值的问题,首先创建一个双端队列,在java中,LinkedList底层实现就是双向链表,用它存储最大值的数组下标。  如果队列不为空并且队列尾部的值nums[qres.peekLast()] <= nums[i],就将尾部的值弹出,直到队列为空或者nums[qres.peekLast()] > nums[i],此时就将这个下标值i进队  当窗口的左边界的下标i-k==qres.peekFirst(),就弹出头元素,因为此时该元素已经不在窗口内,过期了。剩下的情况就是当窗口长度完全为3之后,每次移动都获取队头元素即可

class Solution {
    static LinkedList<Integer> qres = new LinkedList<Integer>();
    public static int[] maxSlidingWindow(int[] arr,int k) {
        qres.clear();
        if(arr == null || arr.length == 0)
            return new int[] {};
        int index = 0;
        int[] res = new int[arr.length - k + 1];
        for(int i = 0;i < arr.length;i++) {
            while(!qres.isEmpty() && arr[qres.peekLast()] <= arr[i])
                qres.removeLast();
            qres.addLast(i);
            if(qres.peekFirst() == i - k)
                qres.removeFirst();
            if(i >= k - 1)
                res[index++] = arr[qres.peekFirst()];
        }
        return res;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode45. 跳跃游戏 II

     还是以样例为例,[2,3,1,1,4],起点是nums[0] = 2,那么在nums[1] = 3和nums[2] = 1中我们应该选择哪个进行跳跃?很...

    mathor
  • 从暴力递归到动态规划

     动态规划没有那么难,但是很多老师在讲课的过程中讲的并不好,由此写下一篇文章记录学习过程

    mathor
  • Manacher算法

     求最大回文子串的长度一般要看原串的长度是奇数还是偶数,然后分别求得,但Manacher算法的第一个神奇之处就是把两种字符串都化为长度为奇数,从而简化计算:

    mathor
  • [日常] Go语言圣经-竞争条件习题

    练习 9.1: 给gopl.io/ch9/bank1程序添加一个Withdraw(amount int)取款函数。其返回结果应该要表明事务是成功了还是因为没有足...

    陶士涵
  • 视频 | MIT和FB搞了个视频数据集,让Youtube视频审查更容易

    创建这样的数据集是一项非常艰巨的工作,因为它包含超过 50 万个视频,为 200 个不同的活动提供近 200 万个注释,并且还有很多预处理步骤需要执行才能使其可...

    AI科技评论
  • LeetCode 128. 最长连续序列(哈希set)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-consecutive-sequenc...

    Michael阿明
  • 19.Linux-USB总线驱动分析

    如下图所示,以windows为例,我们插上一个没有USB设备驱动的USB,就会提示你安装驱动程序 ? 为什么一插上就有会提示信息? 是因为windows自带了...

    张诺谦
  • 刷题第10篇:从完全平方到零钱兑换

    不难看出,这道题目的状态转移方程为:nums[n] = Math.min(nums[n],nums[n - i* i] + 1),我们可以使用迭代的方法,不断的...

    鹏-程-万-里
  • 小心 base64 编码数据拖慢你的后台服务

    今天,同事小赵接到客户导入新闻数据要求,由客户提供新闻数据。于是小赵通过 SQL 脚本把新闻数据入库后,发现前台展示新闻特别慢。幸好当时是晚上凌晨1点,用户比较...

    编筐少年
  • 【戴嘉乐】(进阶)基于IPFS和Ngrok构建自维护资源网关

    上篇文章《【应用】(入门)基于IPFS和Ngrok构建自维护资源网关》,我们通过Ngrok为IPFS节点配置HTTP Tunnels,充分利用了其NAT穿越的特...

    圆方圆学院

扫码关注云+社区

领取腾讯云代金券