12-滑动窗口和单调栈
滑动窗口
定义
-
滑动窗口是一种想象出来的数据结构：
-
滑动窗口有左边界L和有边界R
-
在数组或者字符串或者一个序列上，记为S，窗口就是S[L…R]这一部分
-
L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
-
L和R都只能往右滑
滑动窗口内的最大值
我们通过L和R来确定一个窗口，但不管L还是R滑动之后，都会让窗口呈现新状况。
如何能够更快的得到窗口当前状况下的最大值和最小值？
最好平均下来复杂度能做到O(1)
利用单调双端队列，双端队列可从尾部出，也从头部出。
以最大值为例，思路为：
通过双向队列，构建一个最大值的优先集。
双向队列从头到尾，值是从大到小。
如果R移动，即新的数需要从尾部，加入到双端队列。因为双端队列需要维持从大到小的数据状态。
所以新来的数如果大于队列尾部，则将队列该数从尾部出队，然后继续比较队列尾部的数，不断弹出，找到能够入队。如果小于，就直接加入队列尾部。
因为我们需要的是最大值，所有可以将一些数舍弃扔掉，但仍能保证最大值的更新结构。
如果L移动，我们可以通过加入数的下标判断是否过期。过期即是L移动，队列中的最大值已不在窗口范围内，即是过期。
通过下标判断先过期还是晚过期。如果值相等，保留晚过期的，扔掉下标早过期的。
代码：
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;
//R代表从index 0 开始依次进窗口
for (int R = 0; R < arr.length; R++) {
//进窗口
//双端队列不为空，且队列尾部小于当前入队的数，则不断弹出，直到能够将数放下
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
qmax.pollLast();
}
//上面满足的放入队列的大小判断，此时将其入队
qmax.addLast(R);
//如果窗口没形成W长度，不弹出数字
//R-W为过期下标，所以当头部为过期下标，就弹出。
if (qmax.peekFirst() == R - w) {
qmax.pollFirst();
}
//判断是否开始收集答案
// R >= W-1 则是当形成窗口时，开始每一次收集值。当R来到index(2)，则已经满足3个数，以后每一次都收集值。
if (R >= w - 1) {
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}
整形数组中子数组最大值减最小值达标的子数组个数
给定一个整型数组arr，和一个整数num。某个arr中的子数组sub，如果想达标。必须满足：sub中最大值 – sub中最小值 <= num。
返回arr中达标子数组的数量
仔细分析题目，我们可以想出。
如果一个范围达标，那么在此范围基础上，缩小范围也必达标。
如果一个范围不达标，那么在此范围基础上，扩大范围也必不达标。
那么此问题就可以用滑动窗口解决，且时间复杂度为O(N)。
public static int num(int[] arr, int sum) {
if (arr == null || arr.length == 0 || sum < 0) {
return 0;
}
int N = arr.length;
int count = 0;
LinkedList<Integer> maxWindow = new LinkedList<>();
LinkedList<Integer> minWindow = new LinkedList<>();
int R = 0;
for (int L = 0; L < N; L++) {
//R往右扩到最后一个达标的位置
while (R < N) {
//维持最大值的双端队列
while (!maxWindow.isEmpty() && arr[maxWindow.peekLast()] <= arr[R]) {
maxWindow.pollLast();
}
maxWindow.addLast(R);
//维持最小值的双端队列
while (!minWindow.isEmpty() && arr[minWindow.peekLast()] >= arr[R]) {
minWindow.pollLast();
}
minWindow.addLast(R);
//判断是否达标，不达标，break
if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] > sum) {
break;
} else {
R++;
}
}
//以L为开头，到R位置的可能性
count += R - L;
//判断L是否过期，然后进入下一次循环，即找L++的可能
if (maxWindow.peekFirst() == L) {
maxWindow.pollFirst();
}
if (minWindow.peekFirst() == L) {
minWindow.pollFirst();
}
}
return count;
}
单调栈
定义：
单调栈，一种特别设计的栈结构，为了解决如下的问题：
给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息。
- arr[i]的左侧离i最近，并且小于(或者大于)arr[i]的数在哪？
- arr[i]的右侧离i最近，并且小于(或者大于)arr[i]的数在哪？
如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。
不考虑时间复杂度，直接双重for循环可以很简单得到答案。但时间复杂度为O(N)
无重复值的单调栈
对于数组arr是否有重复值，单调栈有不同的设计。
对于无重复值：
设计一个栈，栈底到栈顶，值是从小到大的。
然后开始遍历arr数组。
从0位置的数开始，不断入栈。
因为栈里的值是从小到大的，所以如果要入栈的数比栈顶的大，直接入栈。
要入栈的数比栈顶小，就弹出，并记录结果。
迫使其弹出的数，即为右侧最近且小于其的数。弹出的数压着的为左侧最近且小于其的数。
public static int[][] getNearLessNoRepeat(int[] arr) {
//每个位置的信息
//如[0][-1, 1]，记录的是下标为0的数。左侧小于其数的下标与右侧小于其的数的下标
int[][] res = new int[arr.length][2];
// 只存位置！
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) { // 当遍历到i位置的数，arr[i]
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
int j = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[j][0] = leftLessIndex;
res[j][1] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) {
int j = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[j][0] = leftLessIndex;
res[j][1] = -1;
}
return res;
}
有重复值的单调栈
与无重复的不同，压入栈的，是一个list，记录的是值下标。
但栈的结构，仍然根据值，从小到大往上排。
如果有相同的值，就将下标添加到，那个对应值的list中。
弹出时，弹出list中最后的那个。
因为list的下标是按照顺序添加的，弹出，也要弹出最后，即最近的那个。
public static int[][] getNearLess(int[] arr) {
//每个位置的信息
int[][] res = new int[arr.length][2];
//栈放的是 值的下标的list，相同值的下标放一起
Stack<List<Integer>> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈
//栈不为空，且栈顶的值大于当前值。（通过下标获取值）
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
//弹出list
List<Integer> popIs = stack.pop();
//弹出后，栈为空，即左侧最小 记录为 -1 。弹出不为空，左侧最小即是栈顶链表的最后的下标，代表的数。将下标记录
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popi : popIs) {
res[popi][0] = leftLessIndex;
//右侧最小为当前位置
res[popi][1] = i;
}
}
//栈不为空，且栈顶值与当前值相等
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(Integer.valueOf(i));
}
//需要重新建list，并压栈
else {
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
//循环完成，且栈不为空，将栈中的值，进行清算
while (!stack.isEmpty()) {
List<Integer> popIs = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popi : popIs) {
res[popi][0] = leftLessIndex;
res[popi][1] = -1;
}
}
return res;
}
例题：柱状图中最大的矩形
https://leetcode.com/problems/largest-rectangle-in-histogram
public static int largestRectangleArea1(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
stack.push(i);
}
while (!stack.isEmpty()) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
public static int largestRectangleArea2(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int N = height.length;
int[] stack = new int[N];
int si = -1;
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
while (si != -1 && height[i] <= height[stack[si]]) {
int j = stack[si--];
int k = si == -1 ? -1 : stack[si];
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
stack[++si] = i;
}
while (si != -1) {
int j = stack[si--];
int k = si == -1 ? -1 : stack[si];
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
例题：最大矩形
public static int maximalRectangle(char[][] map) {
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
int maxArea = 0;
int[] height = new int[map[0].length];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
height[j] = map[i][j] == '0' ? 0 : height[j] + 1;
}
maxArea = Math.max(maxRecFromBottom(height), maxArea);
}
return maxArea;
}
// height是正方图数组
public static int maxRecFromBottom(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
stack.push(i);
}
while (!stack.isEmpty()) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
例题：统计全1子矩形
https://leetcode.cn/problems/count-submatrices-with-all-ones/
public static int numSubmat(int[][] mat) {
if (mat == null || mat.length == 0 || mat[0].length == 0) {
return 0;
}
int nums = 0;
int[] height = new int[mat[0].length];
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[0].length; j++) {
height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;
}
nums += countFromBottom(height);
}
return nums;
}
// 比如
// 1
// 1
// 1 1
// 1 1 1
// 1 1 1
// 1 1 1
//
// 2 .... 6 .... 9
// 如上图，假设在6位置，1的高度为6
// 在6位置的左边，离6位置最近、且小于高度6的位置是2，2位置的高度是3
// 在6位置的右边，离6位置最近、且小于高度6的位置是9，9位置的高度是4
// 此时我们求什么？
// 1) 求在3~8范围上，必须以高度6作为高的矩形，有几个？
// 2) 求在3~8范围上，必须以高度5作为高的矩形，有几个？
// 也就是说，<=4的高度，一律不求
// 那么，1) 求必须以位置6的高度6作为高的矩形，有几个？
// 3..3 3..4 3..5 3..6 3..7 3..8
// 4..4 4..5 4..6 4..7 4..8
// 5..5 5..6 5..7 5..8
// 6..6 6..7 6..8
// 7..7 7..8
// 8..8
// 这么多！= 21 = (9 - 2 - 1) * (9 - 2) / 2
// 这就是任何一个数字从栈里弹出的时候，计算矩形数量的方式
public static int countFromBottom(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int nums = 0;
int[] stack = new int[height.length];
int si = -1;
for (int i = 0; i < height.length; i++) {
while (si != -1 && height[stack[si]] >= height[i]) {
int cur = stack[si--];
if (height[cur] > height[i]) {
int left = si == -1 ? -1 : stack[si];
int n = i - left - 1;
int down = Math.max(left == -1 ? 0 : height[left], height[i]);
nums += (height[cur] - down) * num(n);
}
}
stack[++si] = i;
}
while (si != -1) {
int cur = stack[si--];
int left = si == -1 ? -1 : stack[si];
int n = height.length - left - 1;
int down = left == -1 ? 0 : height[left];
nums += (height[cur] - down) * num(n);
}
return nums;
}
public static int num(int n) {
return ((n * (1 + n)) >> 1);
}
12-滑动窗口和单调栈
https://blog.isle.ink//archives/hua-dong-chuang-kou-he-dan-diao-zhan