左神算法：生成窗口最大值数组（Java版）

本文主要是介绍左神算法：生成窗口最大值数组（Java版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本题来自左神《程序员面试代码指南》“生成窗口最大值数组”题目。

题目

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

例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：

               窗口数组               最大值  [4  3  5] 4  3  3  6  7        54 [3  5  4] 3  3  6  7         54  3 [5  4  3] 3  6  7         54  3  5 [4  3  3] 6  7         44  3  5  4 [3  3  6] 7         64  3  5  4  3 [3  6  7]        7

如果数组长度为 n，窗口大小为 w，则一共产生 n-w+1 个窗口的最大值。

请实现一个函数，

输入：整型数组 arr，窗口大小为 w；
输出：一个长度为 n-w+1 的数组 res，res[i] 表示每一种窗口状态下的最大值。

以本题为例，结果应该返回[5,5,5,4,6,7]

题解

思路总结：每一次从队尾将 小于等于 当前元素的弹出
在这里插入图片描述

代码


import java.util.LinkedList;public class Main {public static int[] getMaxWindow(int[] arr, int w) {if (arr == null || w < 1 || arr.length < w) {return null;}LinkedList<Integer> qmax = new LinkedList<Integer>();int[] res = new int[arr.length - w + 1];int index = 0;for (int i = 0; i < arr.length; i++) {while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) { // 一直弹出队尾位置，直到队尾对应元素大于当前元素为止qmax.pollLast();}qmax.addLast(i); // 放入当前元素if (qmax.peekFirst() == i - w) { // 如果qmax对头下标过期（已在当前窗口覆盖范围之外），则弹出对头下标qmax.pollFirst();}if (i >= w - 1) { // 如果当前i及其以前的元素满足一个窗口大小，则记录当前窗口的最大值res[index++] = arr[qmax.peekFirst()];}}return res;}// for testpublic static void printArray(int[] arr) {for (int i = 0; i != arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};int w = 3;printArray(getMaxWindow(arr, w));}
}