提示：重要基础算法！！
提示：重要基础算法！！
提示：重要基础算法！！
之前咱们刚刚学过单调栈1：
（1）单调栈1：o(1)复杂度求数组arr在窗口w内的最大值或者最小值
之前这个是系统双向队列实现的双向栈，适用于寻找L–R窗口内的最大值，最小值！
今天咱们来说系统栈实现的单调栈，适用于求数组arr中i位置左边距离i最近的比i小的位置L，右边距离i最近的比i小的位置R！
关于单调栈的知识点，一定要学会，今后很大互联网大厂的题目会用到这个俩基础的算法！
关于单调栈的知识点，一定要学会，今后很大互联网大厂的题目会用到这个俩基础的算法！
关于单调栈的知识点，一定要学会，今后很大互联网大厂的题目会用到这个俩基础的算法！
文章目录
- 单调栈2：寻找数组arr中i位置左边距离i最近的比i小的位置L，右边距离i最近的比i小的位置R
- @[TOC](文章目录)
- 高频题引入什么是单调栈2？
- 一、审题
- 暴力解宏观调度，每一个i收集一个答案
- 这就是咱们案例中的结果： 
- 单调栈将复杂度优化到o(n)
- 不妨设arr中没有重复的元素
- 如果arr中有重复的元素，栈里面放列表，存相同的元素的位置们
- 总结
寻找数组arr中，每一个i=0–N-1位置，左边距离i最近的比i小的位置L，右边距离i最近的比i小的位置R
如果左边没有比i小的，那就-1，右边没有比i小的，那就-1
一、审题
示例：
arr=3 2 1 7 0 4 5 6
i = 0 1 2 3 4 5 6 7
每一个位置i，左边最近的比[i]小的位置L，右边最近的比[i]小的位置R
如下图所示
暴力解宏观调度，每一个i收集一个答案
来到i，咱们让L从i-1开始找，—找到i=0，如果都没有找到比[i]小的，那就是L=-1，否则就是L
与此同时，咱们让R从i+1开始找，—找到i=N-1，如果都没有找到比[i]小的，那就是L=-1，否则就是R
这样的话，每一个i都需要o(n)的时间复杂度寻找L,R
外围i从0–N-1遍历一遍需要o(n0
所以整体时间复杂度o(n^2)，可不
代码可以写，用来验证优化算法是否正确，但是复杂度高，做一个了解：
//暴力解
// 参数：输入：int[] arr,返回：所以位置的俩数int[]{a,b}左边，右边
public static int[][] getLeftAndRightMinIndex(int[] arr) {
int[][] res = new int[arr.length][2];
if (arr == null || arr.length == 0) return res;//全0
HashMap lMap = new HashMap<>();
HashMap rMap = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
//找左边的
for (int j = i - 1; j >= 0; j--) {
if (arr[j] < arr[i]) {
lMap.put(i, j);
break;
}
lMap.put(i, -1);//没有就填-1
}
//找右边的
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[i]) {
rMap.put(i, j);
break;
}
rMap.put(i, -1);//没有就填-1
}
//这里特殊值得考虑到位
if (i == 0) lMap.put(i, -1);
if (i == arr.length - 1) rMap.put(i, -1);
}
for (int k = 0; k < arr.length; k++) {
res[k][0] = lMap.get(k);
res[k][1] = rMap.get(k);
}
return res;
}
public static void test(){
int[] arr = {3,2,1,7,0,4,5,6};
int[][] res = getLeftAndRightMinIndex(arr);
for (int k = 0; k < arr.length; k++) {
for (int i = 0; i < 2; i++) {
System.out.print(res[k][i]+" ");
}
System.out.println();
}
}
果不出所料，问题不大：
-1 1 -1 2 -1 4 2 4 -1 -1 4 -1 5 -1 6 -1这就是咱们案例中的结果：
单调栈将复杂度优化到o(n)
上面说了，暴力解，来到i处，还需要咱们遍历寻找左右比[i]小的L,R
能否省掉这个过程？
当然可以！
利用系统栈的单调性解决，咱们设计一个从上到下是降序的单调栈stack！
每次进来的数必须保证是上大下小，如果来了个比栈顶还小的数x，自然把栈顶peek逼走弹出！
直到x比栈顶还大才能进栈。
注意，x进栈之前，先把刚刚弹出的栈顶结算了！
注意，x进栈之前，先把刚刚弹出的栈顶结算了！
注意，x进栈之前，先把刚刚弹出的栈顶结算了！
为啥要结算呢？
因为原本栈顶peek下面【peek下面压的自然就是L】，也就是数组中peek的左边最近还比自己小的位置L，就在peek这压着呢，
现在x来了，比栈顶peek小（也就是数组中peek的右边最近的比peek还小的x来了,【x自然就是R】）
巧不巧？
咱们要求的就是这俩啊：L,R，所以需要结算弹出的栈顶！！！
秒不妙？？？
这个结算栈顶的方式，每次只看peek下面压着谁？L， 新来的比我小的是谁？R，就o(1)复杂度搞定的事情。
——这就是单调栈牛逼的地方，把原来向左，向右搜索的过程，利用栈的单调性，优化并避免了搜索，直接拿下面，上面，结算了。
结果ans就是N*2维的数组，0列表示L，1列表示R，这easy，看案例就知道！
不妨设arr中没有重复的元素好，上面的单调栈的思想，咱们理解了，
现在，咱们用例子来过一下，单调栈是如何优化到用o(n)复杂度搞定的
仍然是案例那个例子
arr=3 2 1 7 0 4 5 6
i = 0 1 2 3 4 5 6 7
看下图：单调栈，存i，上大下小
（1）i=0，进栈
（2）i=1，因为peek=0，i=1对应的2
（3）i=2，因为peek=1，i=2对应的1
（4）i=3，因为peek=2，i=3对应的7>peek=0对应的1，没有破坏了单调性，直接进栈；
（5）i=4，因为peek=3，i=4对应的0
（6）i=5，因为peek=4，i=5对应的4>peek=4对应的0，没有破坏了单调性，i=5直接进栈；
（7）i=6，因为peek=5，i=6对应的5>peek=5对应的4，没有破坏了单调性，i=6直接进栈；
（8）i=7，因为peek=6，i=7对应的6>peek=6对应的5，没有破坏了单调性，i=7直接进栈；
arr遍历结束，单独处理栈
每一个栈顶上面都没有元素，所以大家的R都是=-1
每次结算栈顶peek时，它压着谁，谁就是左边L；
（9）结算peek=7的结果（peek=7压着6的），L=6，R-1；
（10）结算peek=6的结果（peek=6压着5的），L=5，R-1；
（11）结算peek=5的结果（peek=5压着4的），L=4，R-1；
（12）结算peek=4的结果（peek=4下面是空），L=-1，R-1；
整个过程走完，ans全部统计完成！——这个流程，希望你自己去画图，自己走一遍，否则你是无法理解的
咱们整个过程其实就在干一件事：
左边压着L，peek是要结算的栈顶，右边来了个R小于peek，就需要结算peek，
这样L就是左边最近小于peek的，R就是右边最近的小于peek的。
如果arr中有重复的元素，栈里面放列表，存相同的元素的位置们
好，理解了没有重复元素的那个流程
下面咱们来看真的任意数组arr，可能会有重复值
请问你咋办？
arr=3 2 1 7 7 7 0 4 5 6
i = 0 1 2 3 4 5 6 7 8 9
其实进栈结算的逻辑是跟上面一模一样的，只不过，栈里面存在不再是int类型的一个数，而是List列表！
列表放相同的arri的位置们（比如777的位置们3 4 5）
现在，来了i=6位置对应的0，显然破坏了栈的单调性，需要弹出栈顶的列表，
然后结算栈顶的list，结算时，所有的列表list的位置们（3 4 5），都需要结算哦！！！
比如：下图
弹出的list=3 4 5,他们全部的R=i=6,他们全部的左边是L=此时新栈顶那个list【2】的末端位置M-1那个，当然这里是0，因为M=1；
为啥是此时新栈顶那个list【2】的末端位置呢？
万一新栈顶pnew还有几个相同的1呢？比如是0 1 2 三个位置都是1，那3 4 5的左边就只能是L=2，因为2举例3 4 5 都是最近的小于3 4 5对应的7的。
OK捋清了吧！！
真正的单调栈，肯定要考虑数组arr是重复的情况，所以咱们来手撕代码实现上述流程吧！
（0）遍历每一个位置i，方便收集答案
（1）一上来，先看看需要弹出栈顶收集答案吗？需要的话，看栈空吗？空：L=-1，否则L就是此时新栈顶pNew的末尾位置那个i
他们的R是此刻的i；
（2）（1）走完，咱们就要压栈i进去，注意，如果栈顶已经存在了arr[i]，添加即可，否则要新建list
（3）如果i=N了那越界出来了，还要处理栈中剩下的元素们，结算他们，他们所有的R=-1;如果最新的栈顶pNew不空，则L就是pNew的末尾位置那个i，空的话L=-1；
整个过程就是保持栈顶peek左边小，右边小，切都是最近的位置i，结算peek也就很简单了！！！
手撕代码：
//复习：
//真正的单调栈，肯定要考虑数组arr是重复的情况，所以咱们来手撕代码实现上述流程吧！
public static int[][] getLeftRightNearestLessiPosition(int[] arr){
if (arr == null || arr.length == 0) return null;
int N = arr.length;
int[][] ans = new int[N][2];//结果0L,1R
//用栈搞定
Stack> stack = new Stack<>();
//（0）遍历每一个位置i，方便收集答案
for (int i = 0; i < N; i++) {
//（1）一上来，先看看需要弹出栈顶收集答案吗？因为每次我们面对的i都可能收集答案，除了第一次i=0
while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]){
// 需要的话，看栈空吗？空：L=-1，否则L就是此时新栈顶pNew的末尾位置那个i
//他们的R是此刻的i；
List list = stack.pop();//先弹出来
int R = i;
int L = stack.isEmpty() ? - 1 : stack.peek().get(stack.size() - 1);//新栈顶的末尾位置
for(Integer j:list){
ans[j][0] = L;
ans[j][1] = R;
}
}
//（2）（1）走完，咱们就要压栈i进去
//注意，如果栈顶已经存在了，添加即可，否则要新建list
if (!stack.isEmpty() && arr[i] == stack.peek().get(0)){
//有了
stack.peek().add(i);
}else {
//没有的话
List list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
//（3）如果i=N了那越界出来了，还要处理栈中剩下的元素们，结算他们，
// 他们所有的R=-1;如果最新的栈顶pNew不空，则L就是pNew的末尾位置那个i，空的话L=-1；
while (!stack.isEmpty()){
// 需要的话，看栈空吗？空：L=-1，否则L就是此时新栈顶pNew的末尾位置那个i
//他们的R是此刻的i；
List list = stack.pop();//先弹出来
int R = -1;
int L = stack.isEmpty() ? - 1 : stack.peek().get(stack.size() - 1);//新栈顶的末尾位置
for(Integer j:list){
ans[j][0] = L;
ans[j][1] = R;
}
}
return ans;
}
逻辑清晰的话，写代码一点不是问题的！！！
测试一把：
public static void test2(){
int[] arr = {3,2,1,7,0,4,5,6};
int[] arr2 = {3,2,1,7,7,7,0,4,5,6};
System.out.println("arr不重复的话：");
int[][] res = getSubArrayNumWithSingleStack(arr);
for (int k = 0; k < arr.length; k++) {
for (int i = 0; i < 2; i++) {
System.out.print(res[k][i]+" ");
}
System.out.println();
}
System.out.println();
res = getLeftAndRightMinIndex(arr);
for (int k = 0; k < arr.length; k++) {
for (int i = 0; i < 2; i++) {
System.out.print(res[k][i]+" ");
}
System.out.println();
}
System.out.println("arr重复的话：");
res = getSubArrayNumWithSingleStack(arr2);
for (int k = 0; k < arr.length; k++) {
for (int i = 0; i < 2; i++) {
System.out.print(res[k][i]+" ");
}
System.out.println();
}
System.out.println();
res = getLeftAndRightMinIndex(arr2);
for (int k = 0; k < arr.length; k++) {
for (int i = 0; i < 2; i++) {
System.out.print(res[k][i]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
// test();
test2();
}
arr不重复的话： -1 1 -1 2 -1 4 2 4 -1 -1 4 -1 5 -1 6 -1 -1 1 -1 2 -1 4 2 4 -1 -1 4 -1 5 -1 6 -1 arr重复的话： -1 1 -1 2 -1 6 2 6 2 6 2 6 -1 -1 6 -1 -1 1 -1 2 -1 6 2 6 2 6 2 6 -1 -1 6 -1
测试都没问题，所以不重复的arr那个流程理解了，理解重复的arr的代码就很简单了，最终咱们考虑arr是重复的。
总结
提示：重要经验：
1）单调栈的2种形式，一种是求窗口内的最大值最小值，一种是求i左边右边离i最近比i小的位置们
2）充分搞懂单调栈，解决大厂的题目，就游刃有余了!
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
