美文网首页
生成窗口最大值数组

生成窗口最大值数组

作者: Tank_Mao | 来源:发表于2020-10-26 17:38 被阅读0次

【题目】
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边,窗口每次向右滑动一个位置。

例如,数组为[4,3,5,4,3,3,6,7],窗口大小为3时:
[4 3 5] 4 3 3 6 7 窗口中最大值为5
4 [3 5 4] 3 3 6 7 窗口中最大值为5
4 3 [5 4 3] 3 6 7 窗口中最大值为5
4 3 5 [4 3 3] 6 7 窗口中最大值为4
4 3 5 4 [3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7
【要求】
时间复杂度为O(n)

附上源码

package pers.mao.stackAndQueue.demo_07;

import java.util.LinkedList;

/**
 * @author Mao Qingbo
 * @date 2020-10-26
 */
public class Window {
    /**
     *
     * @param arr 输入的整型数组
     * @param w 窗口长度
     * @return res[i]表示每一种窗口状态下的最大值
     */
    public int [] getMaxWindow(int [] arr,int w){
        if(arr == null || w < 1 || arr.length < w){//s非法输入
            return null;
        }
        LinkedList<Integer> qmax = new LinkedList<Integer>();//双端队列qmax,qmax中存放arr中的下标
        int index = 0;//res的下标
        int [] res = new int [arr.length-w+1];
        for(int i = 0; i < arr.length; i++){
            while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);
            if(qmax.peekLast() == i -w){//保证队头不过期
                qmax.pollFirst();
            }
            if(i >= w - 1){
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }
}

相关文章

  • 生成窗口最大值数组

    题目 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 例如,数组为【...

  • 生成窗口最大值数组

    题目 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 例如,数组为[...

  • 生成窗口最大值数组

    【题目】有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边,窗口每次向右滑动一个位置。例如,数组为[...

  • 生成窗口最大值数组

      第一种暴力查找算法,复杂度O(nm),利用双端队列可达到平均O(n)

  • 生成窗口最大值

    题目: 生成窗口最大值数组有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边, 窗口每次向右边滑一个...

  • JZ-064-滑动窗口的最大值

    滑动窗口的最大值 题目描述 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,...

  • 剑指Offer66题

    1、滑动窗口的最大值 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4...

  • 面试题59(剑指offer)--队列的最大值

    题目一: 滑动窗口的最大值。给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。例如,如果输入数组{2,3...

  • 剑指Offer Java版 面试题59:队列的最大值

    题目一:滑动窗口的最大值。给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3...

  • 面试题59:队列的最大值

    题目 滑动窗口的最大值给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。例如,如果输入数组{2,3,4,...

网友评论

      本文标题:生成窗口最大值数组

      本文链接:https://www.haomeiwen.com/subject/mffzmktx.html