提示：重要基础算法！！
提示：重要基础算法！！
提示：重要基础算法！！
这个知识点，一定要学会，今后很大互联网大厂的题目会用到这个基础的算法！
文章目录
- 单调栈1：o(1)复杂度求数组arr在窗口w内的最大值或者最小值
- @[TOC](文章目录)
- 高频题引入什么是单调栈？
- 一、审题
- 暴力解求每个max：o(n*w)复杂度，不可
- 单调栈求max，o(1)复杂度
- 再举例1个给你演示单调栈的绝妙之处！
- 同理，让你求数组arr中w窗口内的最小值，是不是非常简单？
- 总结
给你数组arr，一个定长w的窗口，从左往右滑动，请你求窗口内的最大值，整体返回一个数组ans，代表从左往右每一个窗口内的最大值
一、审题
示例：arr=3 5 2 1 7
数组长为N，窗长为w，则结果数组ans的长度是：N-w+1
暴力解求每个max：o(n*w)复杂度，不可
显然，每次遍历到i位置，你可以从i-w+1–i上遍历一遍，用w长度找max，然后赋值给ans
总共i走N长度，则复杂度：o(n*w)
这不是好的解决方法，咱们想要速度能否快点！！！
一个窗在滑动，每次增加一个数字，吐出去一个数字，能否根据进来的数字，和之前的max对比一下，然后吐出去的数字也跟当前的max对比一下，搞出窗内此刻的最大值max呢？
可以，就是利用双端队列解决这个问题
我们让一个双端队列queue来记录arr的位置i，如果[i]大，尽量放左边
比如
w=3,N=5
arr=3 5 2 1 7
i =0 1 2 3 4
让位置进队列！
（1）0先进去，代表3在最左边，此时3最大
（2）1位置的5来了，因为5>=3所以，可以把3逼走，从尾部弹出【代表有更大的数来了，max可定不是你3】
（3）2位置的2来了，因为2<5，所以，直接进队列，满足让队列左大右小的单调性【这就是所谓的单调栈的意思】
（5）先判断窗口是否过期？如果i-w=队列的头元素，那说明头元素那个arr该出出窗口了。【目前i=2，i-3=-1!=1，还不满足】
（4）此时，发现i>=w-1，说明，此时在arr上已经建立了一个窗口，窗长w组建OK了，此时收集最大值吧，就是队列的头位置那个arr值。
确实就是3 5 2形成了一个窗口，max确实是1位置的5，收集第一个max=5——这就是单调栈的绝妙的地方。它可以用队列维持窗口内的霸主max。
（6）i=3，先看看（1）（2），由于3位置的1<2位置的2，所以可以直接进队列，满足队列左大右小的单调性。然后判断（5），看看队列的头元素是否过期，过期需要让它出窗口，【目前i=3,i-w=3-3=0!=1，还不满足】，再检查（4）收集队列头元素对应的arr值，即max=5，第二个最大值还是5，代表此时窗口内的霸主仍然是5。
（7）i=4，看看（1）（2），由于4位置的7，比3位置的1大，让队尾那个1弹出，循环检查，由于4位置的7，比2位置的2大，所以让队尾的2弹出，循环检查，由于4位置的7比1位置的5大，所以让队尾的5弹出，然后让4进队列。说明新霸主来了，老霸主得滚蛋。
然后判断（5），看看队列的头元素是否过期，过期需要让它出窗口，【目前i=4,i-w=4-3=1!=4，还不满足】，再检查（4）收集队列头元素对应的arr值，即max=7，第3个最大值是7，代表此时窗口内的霸主是7。
其实，整个过程，咱们首在干嘛？
首先干（1）（2），让大的在队列左边，小的在右边【维持单调栈的单调性】，一旦来了新霸主，逼小的滚蛋【队列头那个数，一直维持的是窗口内霸主的位置i】
加完arr[i]之后，随时要检查（5），队列的头元素那个i，是不是已经过期了，如果过期了，需要从头部弹出，代表它不在窗口内了。
每次也要检查（4），窗口w是否形成，形成了就要收集答案，这就是咱本题要求的窗口内的最大值，最大值就是队列头那个i对应的arri。
这个过程，就能保证窗口形成之后，从左往右滑动的过程中，每次收集窗口内的最大值
从左往右遍历o(n)，咱收集了n-w+1个max值
平均收集1个max的时间复杂度为：o(1)
这速度，比暴力o(n*w)快多了吧！
再举例1个给你演示单调栈的绝妙之处！
w=3
arr = 7 6 5 4 3 8
i = 0 1 2 3 4 5
队列q就是咱的单调栈，左边存大，右边小，随时保持单调性
（0）最开始0 1 2仨位置因为可以保持单调性，依次进队列：
此时，发信i=2,i>=w-1=3-1=2,说明窗口形成了，咱们可以收集窗口内的答案了，因为q是单调的，q的头那个0位置对应的7就是此刻的霸主max，ans收集答案：7
（1）i=3位置，4比q队尾2位置对应的5小，故直接进队列，检查此时i-w=队头那个i吗？
i-w=3-3=0,队头是0，竟然相等，说明啥呢？说明窗口太长了，需要把队头弹出！这样才是w=3的窗口长。
此时自然也满足i>=w-1，因为上面已经形成过窗口了，今后都满足这个条件！ans收集答案：7 6
（2）i=4位置，4位置的3比队尾3位置的4小，直接进队尾，保持了单调性，检查此时i-w=队头那个i吗？
i-w=4-3=1,队头是1，竟然相等，说明啥呢？说明窗口太长了，需要把队头弹出！这样才是w=3的窗口长。
ans收集答案：7 6 5
（3）i=5位置，5位置的8比队尾大！！！新霸主来了，为了维持队列的单调性，你就得将队尾弹出，循环弹出，只要霸主比队尾对应的arri大，就要弹出队尾，让新霸主进队列。最终，4 3 2 全部依次弹出！5进队列
检查此时i-w=队头那个i吗？
i-w=5-3=2,队头是5，不相等，说明啥呢？说明窗口仍然是w=3的，不违规。不弹出头哦！！！
ans自然要收集答案：ans:7 6 5 8
i只要到N-1，说明整个arr遍历结束，返回ans
看见没？队列干嘛呢？维持窗口内的霸主的位置i一直在队列的头
只要新来的元素更大，把队尾的位置给逼出去，也就是暂时窗口内霸主才能进队列
每次检查队头的位置是否为i-w，过期要弹出头，保持窗口就w长度。
一旦形成窗口w长，咱就要收集答案到ans中，i=N-1停止。
——这样，每次窗口内的霸主都可以简单地通过队头记录的位置拿到，这就是单调栈的绝妙之处！！
一共举例2个，你仔细体会，仔细品！
手撕代码也就很容易！
//复习单调栈，搞懂思想，手撕代码不是问题
public static int[] singleStackGetMaxValue(int[] arr, int w){
if (arr == null || arr.length == 0) return null;
//队列干嘛呢？**维持窗口内的霸主的位置i一直在队列的头**
LinkedList queue = new LinkedList<>();
int N = arr.length;
int[] ans = new int[N - w + 1];//举个例子就知道结果长度
int index = 0;//索引ans的
//遍历每一个arri
for (int i = 0; i < N; i++) {
//只要新来的元素更大，把队尾的位置给逼出去，也就是暂时窗口内霸主才能进队列
//当然，队列空，就直接加入元素
while (!queue.isEmpty() && arr[i] > arr[queue.peekLast()]) queue.pollLast();
queue.addLast(i);//咱们记录的是arr的位置哦
//每次检查队头的位置是否为i-w，过期要弹出头，保持窗口就w长度。
if (i - w == queue.peekFirst()) queue.pollFirst();//弹出头那个位置，让窗口长度w不变
//一旦形成窗口w长，咱就要收集答案到ans中，i=N-1停止。
if (i >= w - 1) ans[index++] = arr[queue.peekFirst()];//队头位置对应的arri
//——这样，每次窗口内的霸主都可以简单地通过队头记录的位置拿到，这就是单调栈的绝妙之处！！
}
return ans;
}
public static void test(){
int w = 3;
//int[] arr = {4,3,5,4,3,3,6,7};
int[] arr2 = {7,6,5,4,3,8};
int[] res = getMaxArray(arr2, w);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i]+" ");
}
System.out.println();
res = singleStackGetMaxValue(arr2, w);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i]+" ");
}
}
public static void main(String[] args){
test();
}
测试：
7 6 5 8 7 6 5 8
是不是很简单了！！！
同理，让你求数组arr中w窗口内的最小值，是不是非常简单？
给你数组arr，一个定长w的窗口，从左往右滑动，请你求窗口内的最小值，整体返回一个数组ans，代表从左往右每一个窗口内的最小值
仍然，咱们定义一个单调栈，在队头，维持最小值的位置（简称小公主）
下图中，右边是队头了哦！！没事，咱们要做的就是从队尾加入数据，一旦来了更小的小公主，逼走队尾大的数【逻辑和max相反，干的事情很相似的】
保持队列的单调性就行
然后检查过期i-w=队头位置吗？是，就弹出头，让窗口永远维持定长w
每次都要检查i>=w-1吗？是就收集答案ans。i=N-1停止
这个思想跟上面求最大值就是反着来而已，很简单
只需要把求最大值窗口的那个代码，把进队列的条件那个，>号，改为<即可！！！！！！！！
只需要把求最大值窗口的那个代码，把进队列的条件那个，>号，改为<即可！！！！！！！！
只需要把求最大值窗口的那个代码，把进队列的条件那个，>号，改为<即可！！！！！！！！
就这么简单！！！！！！！！！！
你看看下面这个！是不是很容易
//求最小值呢？
//复习单调栈，搞懂思想，手撕代码不是问题
public static int[] singleStackGetMinValue(int[] arr, int w){
if (arr == null || arr.length == 0) return null;
//队列干嘛呢？**维持窗口内的小公主的位置i一直在队列的头**
LinkedList queue = new LinkedList<>();
int N = arr.length;
int[] ans = new int[N - w + 1];//举个例子就知道结果长度
int index = 0;//索引ans的
//遍历每一个arri
for (int i = 0; i < N; i++) {
//只要新来的元素更小，把队尾的位置给逼出去，也就是暂时窗口内小公主才能进队列
//当然，队列空，就直接加入元素
while (!queue.isEmpty() && arr[i] < arr[queue.peekLast()]) queue.pollLast();
queue.addLast(i);//咱们记录的是arr的位置哦——所有的代码，就改了这句中的>为<，太妙了吧
//每次检查队头的位置是否为i-w，过期要弹出头，保持窗口就w长度。
if (i - w == queue.peekFirst()) queue.pollFirst();//弹出头那个位置，让窗口长度w不变
//一旦形成窗口w长，咱就要收集答案到ans中，i=N-1停止。
if (i >= w - 1) ans[index++] = arr[queue.peekFirst()];//队头位置对应的arri
//——这样，每次窗口内的霸主都可以简单地通过队头记录的位置拿到，这就是单调栈的绝妙之处！！
}
return ans;
}
public static void test(){
int w = 3;
//int[] arr = {4,3,5,4,3,3,6,7};
int[] arr2 = {7,6,5,4,3,8};
int[] res = getMaxArray(arr2, w);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i]+" ");
}
System.out.println();
res = singleStackGetMaxValue(arr2, w);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i]+" ");
}
System.out.println();
res = singleStackGetMinValue(arr2, w);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i]+" ");
}
}
public static void main(String[] args){
test();
}
结果：
7 6 5 8 7 6 5 8 5 4 3 3
没错，min就是5 4 3 3
是不是超级超级简单！！
只要你搞懂max那个逻辑，这个代码，太太太容易了。
你不用背的，画个图就知道了
总结
提示：重要经验：
1）单调栈本质就是让双端队列LinkedList头保持最大，尾部保持最小的单调性，只要来了新元素，更大，需要把队尾弹出；过期需要把队头弹出，窗口形成需要把答案收集起来。
2）单调栈求max逻辑捋清了，自然单调栈求min就太太太简单了，只需要把求max的代码中进队列的条件>改<就行。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
