1 单调栈和窗口及其更新结构
1.1 窗口
1.1.1 滑动窗口是什么？
窗口只是我们脑海中的一个范围，用过L和R来规定我们窗口的边界。保证L<=R这个条件
1、滑动窗口是一种想象出来的数据结构；
2、滑动窗口有左边界L和右边界R
3、在数组或者字符串或者一个序列上，记为S,窗口就是S[L…R]这一部分
4、L往右滑动意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
5、 L和R都只能往右滑动
1.1.2 滑动窗口能做什么？
滑动窗口、首尾指针等技巧，说白了就是一种求解问题的流程设计。
1.1.3 维护窗口滑动的更新结构
例如我们求窗口内最大值问题
用单调双端队列来实现，双端队列就是我们的双向链表结构。我们保证我们的双端队列从头部到尾部数值是从大到小的
1、 如果窗口的R位置往右移动，我们把进入窗口的这个数从尾部加入到双端队列。如果当前数比该数的前一个数大（从尾部看）那么队列中小于等于的数弹出。直到小于队列的前一个数，加入该数。
2、如果窗口的L位置往右移动，预示着有数要出我们的窗口，我们从双端队列的头部观看要出去的数是不是我们头部队列的数。是就弹出头部的数，不是就不做任何操作
3、我们窗口结构一直被维护，双端队列右边进，左边出。那么窗口的最大值就是我们双端队列最左侧（头部）的值
==双端队列结构实质上指的是：如果此时形成的窗口状况，不想让R往右动了，而让L往右动。谁会以此成为最大值的优先级。为什么弹出的数不再找回，原因是在窗口滑动的过程中，被弹出的数的优先级已经被后来的大数取代了，这就是尾端加入，前一个数比当前数小则弹出，比当前数大就加入当前数的道理==
反之，如果我们要窗口内最小值，只需要维护我们的双端队列单调递增的，既由小到大的即可
复杂度：窗口滑动经过的数，最多进双端队列一次，最多出双端队列一次，如果窗口滑动了N个数，时间复杂度就是O(N)，单次平均O(1)。
1.1.4 高频题：求滑动窗口最大值
假设一个固定大小为W的窗口，以此划过arr，返回每一次划出状况的最大值
例如，arr=[4, 3, 5, 4, 3, 3, 6, 7]
返回：[5, 5, 5, 4, 6, 7]
分析：窗口起始是4,3,5,窗口内最大值是5。窗口向右滑动变为3,5,4最大值5……
package class01;
import java.util.LinkedList;
public class Code01_SlidingWindowMaxArray {
public static int[] getMaxWindow(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
return null;
}
// Java中LinkedList就是双端队列，双向链表
// 其中放的是下标位置，头代表 （大->小）尾
LinkedList<Integer> qmax = new LinkedList<Integer>();
// 窗口在滑动的过程中，最终会生成arr长度-窗口起始宽度+1个值
int[] res = new int[arr.length - w + 1];
int index = 0;
// L...R
// R
for (int R = 0; R < arr.length; R++) { // 当前让 i -> [i] 进窗口 ， i 就是 r
// R 位置的值 可以放在比他大的数后，或者空
// 双端队列不为空，且双端队列尾部的值小于当前要进入窗口的值
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
// 双端队列从尾部弹出
qmax.pollLast();
}
// 经过上述的while，最终把当前进入窗口的数放入双端队列的尾部
qmax.addLast(R);
// 数进来了
// 如果窗口没有形成W的长度之前，不弹出数字的
// 当前下标是R, R-W就是需要过期的下标。
// 如果双端队列的头部保存的下标等于R-W，就头部弹出。实质R-W就是我们原始结构的L下标
if (qmax.peekFirst() == R - w) {
qmax.pollFirst();
}
// 以上窗口更新做完了
// 窗口没有形成W长度之前，不收集答案。形成W长度后，每一次收集一个答案
if (R >= w - 1) {
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}
// for test
public static int[] rightWay(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
return null;
}
int[] res = new int[arr.length - w + 1];
int index = 0;
int L = 0;
int R = w - 1;
while (R < arr.length) {
int max = arr[L];
for (int i = L + 1; i <= R; i++) {
max = Math.max(max, arr[i]);
}
res[index++] = max;
L++;
R++;
}
return res;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * (maxValue + 1));
}
return arr;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int testTime = 100000;
int maxSize = 100;
int maxValue = 100;
System.out.println("test begin");
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
int w = (int) (Math.random() * (arr.length + 1));
int[] ans1 = getMaxWindow(arr, w);
int[] ans2 = rightWay(arr, w);
if (!isEqual(ans1, ans2)) {
System.out.println("Oops!");
}
}
System.out.println("test finish");
}
}
1.1.5 高频题二：达标子数组数量问题
给定一个整形数组arr，和衣蛾整数num。某个arr中的子数组sub，如果想达标，必须满足:sub中最大值-sub中最小值<=num，返回arr中达标子数组的数量
子数组是连续的
结论1：对于[L…R]范围达标，那么[L…R]上的子数组都达标。max[L…R]肯定比其子数组的max要大，min[L…R]肯定比其范围内的子数组要小，那么[L…R]上满足max - min < num，则其子数组必定满足
同理可得结论2：对于[L…R]范围不达标，那么扩展范围后的[L’…R’]也不达标
我们建立两个双端队列，一个是窗口最大值的双端队列，一个是窗口最小值的双端队列。我们扩展我们的窗口R加1，每扩展一个判断是否仍然达标，达标继续扩展，不达标就停，可以得到本次子数组的达标情况，接着缩小我们的窗口L加1，继续…。窗口滑动不会回退，整体O(N)
package class01;
import java.util.LinkedList;
public class Code02_AllLessNumSubArray {
public static int getNum(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return 0;
}
// 窗口内最小值的更新结构
LinkedList<Integer> qmin = new LinkedList<Integer>();
// 窗口内的最大值的更新结构
LinkedList<Integer> qmax = new LinkedList<Integer>();
int L = 0;
int R = 0;
// [L..R) -> [0,0) 窗口内无数 [1,1)
// [0,1) -> [0~0] 窗口里只有一个数
int res = 0;
// L是开头位置，尝试每一个开头
while (L < arr.length) {
// 如果此时窗口的开头是L,下面的while工作是:R向右扩到违规为止
// R是最后一个达标位置的再下一个，通过下文的break终止
while (R < arr.length) {
// R位置的数进入窗口后，最小值的更新结构和最大值的更新结构都要更新
while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {
qmin.pollLast();
}
qmin.addLast(R);
// R -> arr[R],
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
qmax.pollLast();
}
qmax.addLast(R);
// 如果此时不满足了，break。说明窗口已经成长到了第一个不达标的数进来了
if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
break;
}
R++;
}
// R是最后一个达标位置的再下一个，第一个违规的位置
res += R - L;
// 检查最小值和最大值的更新结构有没有过期
if (qmin.peekFirst() == L) {
qmin.pollFirst();
}
if (qmax.peekFirst() == L) {
qmax.pollFirst();
}
// 窗口左边界向右滑动，窗口容量此时减1
L++;
}
return res;
}
// for test
public static int[] getRandomArray(int len) {
if (len < 0) {
return null;
}
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = (int) (Math.random() * 10);
}
return arr;
}
// for test
public static void printArray(int[] arr) {
if (arr != null) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[] arr = getRandomArray(30);
int num = 5;
printArray(arr);
System.out.println(getNum(arr, num));
}
}
本题根据窗口滑动建立了单调性，上文的结论
1.1.6 如何优化一个问题？
1、 数据状况层面是否可以优化
2、 问题本身是否可以优化。单调性，首位指针（头指针往右走，尾指针往左走）等
遇到一个问题我们先观察，问题本身和范围是否可以建立单调性，至于需要用哪个原型来解决，串口和首位指针法是常见的流程。所以窗口和首位指针主要用来解决单调性的
1.2 单调栈
1.2.1 单调栈结构
在一个数组中，求每一个位置左边离它最近的比它小的数在哪，右边离它最近的比它小的数在哪。
例如[3, 2, 1, 7]。3左边比它小的最近的位置的数的位置没有，为-1，右边是1位置的2。2左边比它小的最近的位置的数的位置没有，为-1，右边是2位置的1等。
用一个map来记录，暴力解O(N^2)。单调栈能够在O(N)解决
单调栈算法流程：
草稿纸上模拟这个栈;
没有相等元素的情况：准备一个栈结构，暂定从小到大的单调栈结构。从左往右遍历我们的数组，[3,4,2,5]，由于栈空，第一个元素可以进栈，3进栈。
1位置的数4可以进栈，因为没有破坏从小到大的栈的单调性。
2位置的2无法直接进栈，因为会破坏栈的单调性。需要弹出栈元素，元素一旦被弹出，生成相应的记录。
1位置的4弹出，右边最近的比你小的数，就是谁让你弹出的数，所以4的右边最近的比4小的数是2。左边最近比你小的数，就是你在栈中压着的数，所以4的左边最近的比4小的数是3。
2位置的2此时仍然无法进栈，因为栈中此时还有3，那么3弹出。3的最近的右侧比3小的数是2，3是栈底元素，没有压着的元素，所以3左侧最近的比3小的数没有，位置置为-1。其他元素同理……。
最后如果没有元素了，栈中元素弹出，此时不是其他元素迫使的弹出，所以自然弹出的右侧最近比它小的无返回-1。左侧最近比它小的看它在栈中是否压着其他元素
可以选择任意位置去证明，证明略
如果存在相等元素的情况，我们栈中每个元素保存为list表示相等元素列表。无法直接进入单调栈时，弹出list最右侧的元素，该元素右侧最近的比自己小的数，就是迫使它弹出的那个数。该元素左侧最近比它小的数，就是自身的这个list压着的的list的最右的数。list的相同元素有两种情况，一种是两个数相等且挨着，另外一种是某个位置释放了中间位置的数后遇到相等元素，进入一个list中去。画栈模拟可看出
package class01;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
public class Code03_MonotonousStack {
// 数组中没有重复值的情况
public static int[][] getNearLessNoRepeat(int[] arr) {
int[][] res = new int[arr.length][2];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
int popIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[popIndex][0] = leftLessIndex;
res[popIndex][1] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) {
int popIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[popIndex][0] = leftLessIndex;
res[popIndex][1] = -1;
}
return res;
}
// arr [3, 2, 1, 4, 5]
// 0 1 2 3 4
// 表示 0这个数左边最近比0小的没有，位置是-1，右边1。1位置数左边最近比0小的没有-1，右边2
// [
// 0 : [-1, 1 ]
// 1 : [-1, 2 ]
// ]
// 数组中存在重复值的情况
public static int[][] getNearLess(int[] arr) {
int[][] res = new int[arr.length][2];
// List<Integer> -> 放的是位置，同样值的东西，位置压在一起
// 代表值 底 -> 顶 小 -> 大
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<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] = i;
}
}
// 相等的、比你小的
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(Integer.valueOf(i));
} 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;
}
// for test
public static int[] getRandomArrayNoRepeat(int size) {
int[] arr = new int[(int) (Math.random() * size) + 1];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
for (int i = 0; i < arr.length; i++) {
int swapIndex = (int) (Math.random() * arr.length);
int tmp = arr[swapIndex];
arr[swapIndex] = arr[i];
arr[i] = tmp;
}
return arr;
}
// for test
public static int[] getRandomArray(int size, int max) {
int[] arr = new int[(int) (Math.random() * size) + 1];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
}
return arr;
}
// for test
public static int[][] rightWay(int[] arr) {
int[][] res = new int[arr.length][2];
for (int i = 0; i < arr.length; i++) {
int leftLessIndex = -1;
int rightLessIndex = -1;
int cur = i - 1;
while (cur >= 0) {
if (arr[cur] < arr[i]) {
leftLessIndex = cur;
break;
}
cur--;
}
cur = i + 1;
while (cur < arr.length) {
if (arr[cur] < arr[i]) {
rightLessIndex = cur;
break;
}
cur++;
}
res[i][0] = leftLessIndex;
res[i][1] = rightLessIndex;
}
return res;
}
// for test
public static boolean isEqual(int[][] res1, int[][] res2) {
if (res1.length != res2.length) {
return false;
}
for (int i = 0; i < res1.length; i++) {
if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
return false;
}
}
return true;
}
// for test
public 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 size = 10;
int max = 20;
int testTimes = 2000000;
for (int i = 0; i < testTimes; i++) {
int[] arr1 = getRandomArrayNoRepeat(size);
int[] arr2 = getRandomArray(size, max);
if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
System.out.println("Oops!");
printArray(arr1);
break;
}
if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
System.out.println("Oops!");
printArray(arr2);
break;
}
}
}
}
1.2.2 单调栈的应用
给定一个只包含正整数的数组arr，arr中任何一个子数组sub，一定都可以算出(sub累加和)*(sub中的最小值)是什么，那么所有子数组中，这个值最大是多少？
package class01;
import java.util.Stack;
public class Code04_AllTimesMinToMax {
public static int max1(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
int minNum = Integer.MAX_VALUE;
int sum = 0;
for (int k = i; k <= j; k++) {
sum += arr[k];
minNum = Math.min(minNum, arr[k]);
}
max = Math.max(max, minNum * sum);
}
}
return max;
}
public static int max2(int[] arr) {
int size = arr.length;
int[] sums = new int[size];
sums[0] = arr[0];
for (int i = 1; i < size; i++) {
sums[i] = sums[i - 1] + arr[i];
}
int max = Integer.MIN_VALUE;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < size; i++) {
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
int j = stack.pop();
max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
}
stack.push(i);
}
while (!stack.isEmpty()) {
int j = stack.pop();
max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
}
return max;
}
public static int[] gerenareRondomArray() {
int[] arr = new int[(int) (Math.random() * 20) + 10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 101);
}
return arr;
}
public static void main(String[] args) {
int testTimes = 2000000;
System.out.println("test begin");
for (int i = 0; i < testTimes; i++) {
int[] arr = gerenareRondomArray();
if (max1(arr) != max2(arr)) {
System.out.println("FUCK!");
break;
}
}
System.out.println("test finish");
}
}