本文主要是介绍左神算法：生成窗口最大值数组（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));}
}
运行结果
5 5 5 4 6 7
这篇关于左神算法：生成窗口最大值数组（Java版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
