网站运营部的职责,8黄页网站建设,响应式网站 解决方案,实时网站制作数据结构与算法---单调栈结构 1 滑动窗口问题 1 滑动窗口问题 1 滑动窗口问题 由一个代表题目#xff0c;引出一种结构
【题目】
有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边#xff0c;窗口每次向右边滑一个位置。 例如#xff0c;数组为[4,3,… 数据结构与算法---单调栈结构 1 滑动窗口问题 1 滑动窗口问题 1 滑动窗口问题 由一个代表题目引出一种结构
【题目】
有一个整型数组 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
如果数组长度为n窗口大小为w则一共产生 n-w1 个窗口的最大值。
请实现一个函数。 输入: 整型数组arr窗口大小为w。
输出:一个长度为 n - w 1的数组resres[i] 表示每一种窗口状态下的最大值 以本题为例,结果应该 返回{5,5,5,4,6,7}
public class SlidingWindowMaxArrTest {public static void main(String[] args) {int[] arr {4, 3, 5, 4, 3, 3, 6, 7};final int w 3;int[] windowMaxArr getWindowMaxArr(arr, w);for (int i 0; i windowMaxArr.length;i){System.out.print(windowMaxArr[i] );}System.out.println();}/*** param arr* param w 窗口的宽度* return*/public static int[] getWindowMaxArr(int[] arr, int w) {if (arr null || arr.length w || w 1) {return null;}/*** 双端队列 存放数组的索引* 队列的头部存放最大值的索引*/LinkedListInteger qMax new LinkedList();// 滑动窗口最大值数组int[] retArr new int[arr.length - w 1];int index 0;for (int i 0; i arr.length; i) {// 放入队列的元素 要保证队列头部的值是最大的// 放入的时候发现队列的最后一个元素没有大于arr[i] 则 弹出while (!qMax.isEmpty() arr[i] arr[qMax.peekLast()]) {qMax.pollLast();}qMax.addLast(i);// 队列中的头部的元素过期if (qMax.peekFirst() i - w) {qMax.pollFirst();}if (i w - 1) {retArr[index] arr[qMax.peekFirst()];}}return retArr;}
}1 滑动窗口问题
