剑指offer系列之六十三:滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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]}。

这实际上可以看成是TCP/IP中差错控制中滑动窗口的算法实现了。由于每次窗口大小是固定的,所以可以创建一个指针用于指向当前窗口的第一个值,而且位置该值是当前窗口的最大值的下标。这么做的好处在于每次窗口移动只需要从第一个位置取值就可以,时间复杂度是O(1)。那么具体需要在获取每个窗口的值得时候与队列中(需要创建一个队列用于保存每个窗口最大值的下标)的队尾指针的元素进行比较,如果比当前遍历到的元素小的话,需要把队尾元素移除,因为我们需要获得的是最大值。这样一直遍历到最后一个元素,就把每个窗口的最大值获取到了。下面是具体的实现代码(已被牛客AC):

package com.rhwayfun.offer;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class MaxNumInWindow {

    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> maxList = new ArrayList<Integer>();
        if(size <= 0) return maxList;
        //创建一个双端队列保存每个滑动窗口的最大值得下标
        ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
        //创建一个变量start用于记录当前滑动窗口的最大值的下标
        int start = 0;
        for (int i = 0; i < num.length; i++) {
            start = i + 1 - size;//当start大于的时候表示第一个窗口已经不能再移动了
            if(queue.isEmpty()){
                queue.add(i);
            }else if(start > queue.peekFirst()){//这个条件表示当前窗口start的值比上一个窗口的start更大
                queue.pollFirst();
            }

            while(!queue.isEmpty() && num[queue.peekLast()] <= num[i]){
                //这种情况表示,队列队尾位置对应的元素比当前元素更小,就移除他,因为需要得到的是窗口最大值
                queue.pollLast();
            }
            queue.add(i);
            if(start >= 0){
                //实际上当start=0的时候第第一个滑动窗口,这时队列中保存的是第一个滑动窗口最大值的下标,直接添加就行
                maxList.add(num[queue.peekFirst()]);
            }
        }
        return maxList;
    }

    public static void main(String[] args) {
        int[] num = {2,3,4,2,6,2,5,1};
        ArrayList<Integer> list = new MaxNumInWindow().maxInWindows(num, 3);
        System.out.println(list);
    }
}
时间: 2024-09-29 10:56:13

剑指offer系列之六十三:滑动窗口的最大值的相关文章

剑指offer系列之六十五:机器人的运动范围

题目描述 地上有一个m行和n列的方格.一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子. 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18.但是,它不能进入方格(35,38),因为3+5+3+8 = 19.请问该机器人能够达到多少个格子? 这题实际与上一题"矩阵中的路径"思路是相似的,都是需要创建一个状态数组对访问的格子进行标记,但是这里需要计算所有能够走的格子总数,实际

剑指offer系列之四十三:扑克牌顺子

题目描述 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)-他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!"红心A,黑桃3,小王,大王,方片5","Oh My God!"不是顺子-..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13.上面的5张牌就可以变成"1,2,3,4,5"(大小王

剑指offer系列之五十三:字符流中第一个不重复的字符

题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符.例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g".当从该字符流中读出前六个字符"google"时,第一个只出现一次的字符是"l". 输出描述: 如果当前字符流没有存在出现一次的字符,返回#字符. 这题与前面的第一个不重复的字符有些重复了,所以直接看代码(已被牛客AC): package com.rhwayfun.offer; impor

剑指offer系列之三十三:第一个只出现一次的字符

题目描述 在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符的位置.若为空串,返回-1.位置索引从0开始 第一个只出现一次的字符是关键,就意味着需要所有的字符进行出现次数的统计,所以我们需要两次遍历:第一次获取每个字符出现的次数:第二次把第一个只出现一次的字符找到.在Java中可以通过HashMap实现对每个字符次数的统计,由于在题目中并没有我们限定使用Java提供的内置结构,所以可以通过这种办法迅速找到第一个只出现一次的字符. 下面是基于这种思路的实现

剑指offer系列之六十四:矩阵中的路径

题目描述 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径.路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子.如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子. 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子. 这实际上是回

剑指offer系列之六十一:二叉树搜索树的第k个节点

题目描述 给定一颗二叉搜索树,请找出其中的第k大的结点.例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4. 因为二叉搜索树是排序的,所以如果需要找出第k个节点只需要进行中序遍历就可以得到第k节点.不过中序遍历的结果就是排序的,所以实质上就是插入排序.可以利用一个集合,在遍历的过程中利用插入排序的算法就能得到第k个节点.下面是这种实现思路的实现代码(已被牛客AC): public class Solution { //采用非递归中序遍历的方式得到第k

剑指offer系列之六十:序列化二叉树

题目描述 请实现两个函数,分别用来序列化和反序列化二叉树 首先得理解题目的意思,序列化就是返回一个带有#和逗号的字符串.反序列化就是根据带有#和逗号的字符串返回一棵二叉树.比如对于二叉树 1 / \ 2 3 /\ /\ 4 5 6 7 来讲,序列化的结果是1,2,#,#,3,4,#,7,#,#,5,#,#,.而反序列化的结果则是输出一棵二叉树. 下面是具体的实现代码(已被牛客AC): String Serialize(TreeNode root) { StringBuilder sb = new

剑指offer系列之十三:链表中的倒数第k个节点

题目描述 输入一个链表,输出该链表中倒数第k个结点. 举一个简单的例子,比如链表{1,2,3,4,5},如果要返回倒数第二个节点,也就是k=2,就相当于正数第5-k+1=4个节点,所以我们可以采用两次循环:一次循环得到链表的结点个数:另一次循环则是从链表中找到第n-k+1个节点.虽然是两次循环,但时间复杂度是O(n),需要注意的是,这里仍然需要对链表的边界条件进行判断.基于这种思路写出如下代码: public ListNode FindKthToTail(ListNode head,int k)

剑指offer系列之六十二:数据流中的中位数

题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值.如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值. 根据题目的意思,就是对数据流中的数据进行排序然后得到其中位数.要解决的关键问题是如何在读入数据的时候就对数据进行排序.实际上可以看成是插入排序算法的应用,可以维持一个List集合,保证每次读入数据集合中的数据都是排序的.基本思路是:从集合的第一个元素开始,依次比较与新读入的元素的大小关系,从而把新读入