Java教程

算法-15生成窗口最大值数组

本文主要是介绍算法-15生成窗口最大值数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

描述

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置,求每一种窗口状态下的最大值。(如果数组长度为n,窗口大小为w,则一共产生n-w+1个窗口的最大值)  

输入描述:

第一行输入n和w,分别代表数组长度和窗口大小 第二行输入n个整数X_iXi​,表示数组中的各个元素

输出描述:

输出一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值

示例1

输入:
8 3
4 3 5 4 3 3 6 7

输出:
5 5 5 4 6 7

说明:
例如,数组为[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

输出的结果为{5 5 5 4 6 7}

思路

使用双端队列来记录一个窗口中,arr 数组的最大值序号。
import java.util.LinkedList;
import java.util.Scanner;

public class Main{
    
    // 双端队列始终维持一个前大后小的结构,随着窗口右移,队列前面的元素会失效
    // 维护队列:如果队尾对应的元素小,弹出不要;如果队尾对应元素大,就把新的数组的下标加进来,继续维护前大后小的结构
    public static int[] getMaxWindow(int[] arr,int w) {
        if(arr == null || w<1||arr.length<w){
            return null;
        }
        //结果为n-w+1长度的数组
        LinkedList<Integer> qMax = new LinkedList<Integer>();
        int[] result = new int[arr.length - w +1];
        int index = 0;
        for(int i=0;i<arr.length;i++){
            // 如果队尾对应的元素比较小,就弹出队尾,直到队尾的位置所代表的值比当前值arr[i]大
            while(!qMax.isEmpty()&&arr[qMax.peekLast()] <= arr[i]) {
                qMax.pollLast();
            }
            qMax.addLast(i);
            
            // 检查队头下标是否过期,过期就把队头弹出
            if(qMax.peekFirst() == i - w){
                qMax.pollFirst();
            }
            // 如果窗口出现了,就开始记录每个窗口的最大值
            if(i >= w -1) {
                result[index++] = arr[qMax.peekFirst()];
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int w = scanner.nextInt();
        int[] arr = new int[n];
        int i = 0;
        while(scanner.hasNext()){
            arr[i++] = scanner.nextInt();
        }
        
        int[] res = getMaxWindow(arr,w);
        StringBuilder sb = new StringBuilder();
        for(int data : res){
            sb.append(data).append(" ");
        }
        System.out.println(sb);
        
    }
    
}

 

这篇关于算法-15生成窗口最大值数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!