首页 > 其他分享 >239. 滑动窗口最大值

239. 滑动窗口最大值

时间:2023-04-17 21:46:45浏览次数:64  
标签:deque nums int 最大值 元素 239 myQueue 滑动 peek

设计单调栈

class Solution {

    class MyQueue{
        Deque<Integer> deque = new LinkedList<>();
        // 弹出元素时,比较当前要弹出的数值是否等于队列出口的数值,如果相等则弹出
        public void poll(int val){
            if(!deque.isEmpty()&&val==deque.peek()){
                deque.poll();
            }
        }

        // 添加元素时,如果要添加的元素大于入口处元素,就将入口处元素弹出
        // 保证队列 大-》小
        
        public void add(int val){
            while(!deque.isEmpty()&& val>deque.peek()){
                deque.removeLast();
            }
            deque.add(val);
        }

        // 得到队首元素,此时队首元素就是最大的
        public int peek(){
            return deque.peek();
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==1){
            return nums;
        }
        int len = nums.length-k+1;
        // 存放结果数组  num是填充时的指针
        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;
    }
}

标签:deque,nums,int,最大值,元素,239,myQueue,滑动,peek
From: https://www.cnblogs.com/chenyi502/p/17327597.html

相关文章

  • Python入门基础实例讲解——两个数字比大小,并输出最大值
    嗨害大家好鸭!我是小熊猫~今天也是给大家带来干货的一天~pycharm永久激活码可以从这里找到我:输出:print()print()方法用于打印输出,最常见的一个函数。比较运算符>:大于,如果运算符前面的值大于后面的值,则返回True;否则返回False<:小于,如果运算符前面的值小于后面的值,则返回True;否......
  • oracel将序列值改为当前系统最大值方法
    --修改序列为表中最大值declareMax_IdNUMBER(10);Current_ValueNUMBER(10);BEGINSELECTmax(to_number(user_code))INTOMax_IdFROMF_USERINFOtwheret.user_code!='u0000000';loopSELECTS_USERCODE.NEXTVALINTOCurrent_ValueFROMdual;......
  • 滑动窗口
    算法简介长度为k的窗口,即为从原数组中连续k位的子数组。滑动窗口即保持窗口的长度为k,且窗口从1~k不断向后移动变为2~k+1,3~k+2,直到n-k+1~n。其中窗口大小不变通过将最左侧数移出窗口,右侧数移入窗口实现时间复杂度\(O(n)\)实现原理假设求滑动窗......
  • 【LBLD】滑动窗口算法延伸:RABIN KARP 字符匹配算法
    滑动窗口算法延伸:RABINKARP字符匹配算法187.重复的DNA序列普通方法:classSolution{public:vector<string>findRepeatedDnaSequences(strings){intn=s.size();unordered_set<string>seen;unordered_set<string>res;......
  • 滑动窗口系列
    滑动窗口适合在题目要求连续的情况下使用相关题目模板:/*滑动窗口算法框架*/voidslidingWindow(strings){//用合适的数据结构记录窗口中的数据unordered_map<char,int>window;intleft=0,right=0;while(right<s.size()){//......
  • 直播平台软件开发,Android代码模拟触摸、点击及滑动等事件
    直播平台软件开发,Android代码模拟触摸、点击及滑动等事件一、应用中模拟物理和屏幕点击事件 例如,模拟对某个view的点击事件 privatevoidsimulateClick(Viewview,floatx,floaty){  longdownTime=SystemClock.uptimeMillis();  finalMotionEventdownEve......
  • [LeetCode] 2390. Removing Stars From a String
    Youaregivenastring s,whichcontainsstars *.Inoneoperation,youcan:Chooseastarin s.Removetheclosest non-star charactertoits left,aswellasremovethestaritself.Return thestringafter all starshavebeenremoved.Note:Thei......
  • 关于滑动窗口算法的应用场景
    算法原理滑动窗口算法是一种基于双指针(又称滑动窗口)的算法,是一种常用的数据处理算法,通常用于解决数组或字符串中的子数组或子串问题。滑动窗口算法的基本思想是使用两个指针left和right来定义一个窗口,窗口内包含满足特定条件的元素子序列,然后不断移动指针left和right来滑动窗口,......
  • 【LeeCode】2399. 检查相同字母间的距离
    【题目描述】给你一个下标从 0 开始的字符串 s ,该字符串仅由小写英文字母组成,s 中的每个字母都 恰好 出现 两次 。另给你一个下标从 0 开始、长度为 26 的的整数数组 distance 。字母表中的每个字母按从 0 到 25 依次编号(即,'a'->0, 'b'->1, 'c'->2,.........
  • mysql的主键超过最大值会发生什么?
    设置主键的情况下在自增主键达到int64最大后,再次插入一行记录,报错如下:Duplicateentry‘4294967295’forkey‘increment_id_test.PRIMARY’唯一键冲突报错:当auto_incement达到上限后,再次申请下一个id时,得到的值保持不变。在建表时,通常都会将主键id设置为8字节的bigintu......