数据结构与算法---单调栈结构

---

 

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-w+1 个窗口的最大值。

请实现一个函数。 输入: 整型数组arr，窗口大小为w。

输出:一个长度为 n - w + 1的数组res，res[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;}/*** 双端队列 存放数组的索引*  队列的头部存放最大值的索引*/LinkedList<Integer> 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 滑动窗口问题