CD101题：单调栈结构

题目链接
https://www.nowcoder.com/ta/programmer-code-interview-guide

// 1. 定义两个数组Left[] 保存左边小值。 Right保存右边小值。
// 2. 定义Stack 保存单调递增的下标值。
// 3.循环遍历整个数组
//栈为空入栈[0(3)]
// 4. 栈不为空，并且当前元素小于栈顶元素 为了维户栈的递增，栈顶出栈。
// cur=1 （4） ，> 栈顶说明 cur 左边的最近小值为0（3），更新
// 元素压入栈中
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner =new Scanner(System.in);
int N =scanner.nextInt();
int[] arr =new int[N];
for(int i=0;i<N;i++){
arr[i]= scanner.nextInt();
}
// 1. 定义一个栈保存下标
Stack<integer> stack =new Stack<>();
// 2.定义 结果集
int[] right= new int[N];
int[] left =new int[N];
// 初始化为-1
for(int i=0;i<N;i++){
left[i]=-1;
right[i]=-1;
}
for(int i=0;i<N;i++){
int cur=arr[i];
while(!stack.empty() && arr[stack.peek()]> cur ){//右边界
right[stack.pop()]=i;//
}
// 当前元素小于栈顶 栈顶元素是当前元素的右边界
if(!stack.empty()){
left[i]= stack.peek();
}
stack.push(i);
}
for (int i=0;i<N;i++){
StringBuilder buffer =new StringBuilder();
buffer.append(left[i]);
buffer.append(" ");
buffer.append(right[i]);
System.out.println(buffer.toString());
}
}
}</integer>