61.滑动窗口的最大值《剑指Offer》(Java版)

不念不忘少年蓝@ 2022-01-30 14:13 140阅读 0赞

## 题目描述 ##

> 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{4,4,6,6,6,5\}； 针对数组\{2,3,4,2,6,2,5,1\}的滑动窗口有以下6个： \{\[2,3,4\],2,6,2,5,1\}， \{2,\[3,4,2\],6,2,5,1\}， \{2,3,\[4,2,6\],2,5,1\}， \{2,3,4,\[2,6,2\],5,1\}， \{2,3,4,2,\[6,2,5\],1\}， \{2,3,4,2,6,\[2,5,1\]\}。

import java.util.*;
    /**
    用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次
    1.判断当前最大值是否过期
    2.新增加的值从队尾开始比较，把所有比他小的值丢掉
    */
    public class Solution {
       public ArrayList<Integer> maxInWindows(int [] num, int size)
        {
            ArrayList<Integer> res = new ArrayList<>();
            if(size == 0) return res;
            int begin; 
            ArrayDeque<Integer> q = new ArrayDeque<>();
            for(int i = 0; i < num.length; i++){
                begin = i - size + 1;
                if(q.isEmpty())
                    q.add(i);
                else if(begin > q.peekFirst())
                    q.pollFirst();
             
                while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                    q.pollLast();
                q.add(i);  
                if(begin >= 0)
                    res.add(num[q.peekFirst()]);
            }
            return res;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关（Java 剑指 offer）滑动窗口的最大值

文章目录一、题目解析二、代码三、总结一、题目解析给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。

本是古典何须时尚/ 2022年12月14日 03:50/ 0 赞/ 113 阅读

相关剑指offer（C++）——滑动窗口的最大值

题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗

淩亂°似流年/ 2022年06月17日 07:22/ 0 赞/ 174 阅读

相关剑指offer_滑动窗口的最大值

/ 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在

拼搏现实的明天。/ 2022年06月08日 23:43/ 0 赞/ 167 阅读

相关剑指offer 滑动窗口的最大值

1、题目给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗

拼搏现实的明天。/ 2022年06月08日 05:55/ 0 赞/ 163 阅读

相关【剑指Offer】64滑动窗口的最大值

题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗

青旅半醒/ 2022年04月11日 08:22/ 0 赞/ 161 阅读

相关剑指offer: 滑动窗口的最大值

题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗

￡神魔★判官ぃ/ 2022年02月25日 15:47/ 0 赞/ 182 阅读

相关剑指Offer-滑动窗口的最大值

题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗

ゝ一世哀愁。/ 2022年02月05日 12:36/ 0 赞/ 192 阅读

相关 61.滑动窗口的最大值《剑指Offer》(Java版)

题目描述 > 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑

不念不忘少年蓝@/ 2022年01月30日 14:13/ 0 赞/ 141 阅读

相关剑指offer 滑动窗口的最大值

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3

╰半橙微兮°/ 2021年10月14日 03:40/ 0 赞/ 260 阅读

相关剑指offer：滑动窗口的最大值

试题：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，

忘是亡心i/ 2021年06月24日 16:10/ 0 赞/ 377 阅读