基本概念
从一个问题引出单调栈的这个概念,给定一个数组,对于数组中的每一个元素,分别找到它左边和右边最近的小于它的元素
无重复数组
默认该数组中的元素是无重复的
我们可以维护一个栈,从栈的下方到上方,元素的大小从小到大.
对于数组中的每一个元素,
如果栈顶的元素小于当前的元素,那么直接将该元素push到栈中
如果栈顶的元素大于当前的元素,那么就要弹出栈顶的元素并直到栈顶的元素小于当前的元素为止.
同时对于那些被弹出的元素,
它们的右边最近的小于它的元素就是该元素,
左边最近的小于它的元素就是栈中它下面的元素
public static int[][] getNearLessNoRepeat(int[] arr){
int n=arr.length;
//res[i][0]保存的是左边的最小最近元素的下标
//res[i][1]保存的是右边的最小最近元素的下标
int[][] res=new int[n][2];
Stack<Integer> stack=new Stack<>();
for (int i = 0; i < n; i++) {
//如果该数字小,就执行退栈操作
while(!stack.isEmpty()&&arr[i]<arr[stack.peek()]){
int index=stack.pop();
int nextindex=stack.isEmpty()?-1:stack.peek();
res[index][0]=nextindex; //栈中的下一个
res[index][1]=i; //该数组元素arr[i]
}
//不然,直接进栈
stack.push(arr[i]);
}
//如果栈中还有剩余
while (!stack.isEmpty()){
int index=stack.pop();
int nextindex=stack.isEmpty()?-1:stack.peek();
res[index][0]=nextindex;
res[index][1]=-1;
}
return res;
}
有重复数组
上面是没有重复数组的情况,对于那些有重复数组的来说,分析方法是一样的,只是栈中原来存放的是数字,现在存放的是链表,链表中存放的都是相同的元素
如果当前数组元素小于栈顶的元素,还是要执行退栈操作直到当前数组元素大于栈顶的元素为止.
同时我们还要记录被退栈的那些元素的,左边右边的临近最小值,右边临近最小值就是该数组元素,左边临近最小值就是它的下方的链表的最尾部元素
如果当前数组元素等于栈顶的元素,那么直接将该元素加入到该栈顶元素的链表的尾部
如果当前数组元素大于栈顶的元素,那么构造出一个链表,将该元素加入到链表中,然后将链表放入栈中
public static int[][] getNearLessRepeat(int[] arr){
int n=arr.length;
int[][] res=new int[n][2];
Stack<List<Integer>> stack=new Stack<>();
for (int i = 0; i < n; i++) {
//如果该数字小,就执行退栈操作
while(!stack.isEmpty()&&arr[i]<arr[stack.peek().get(0)]){
List<Integer> list=stack.pop();
int nextindex=stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
for (Integer x:list){
res[x][0]=nextindex;
res[x][1]=i;
}
}
//不然,直接进栈
if(!stack.isEmpty()&&arr[i]==arr[stack.peek().get(0)]){
stack.peek().add(arr[i]);
}else{
List<Integer> list=new LinkedList<>();
list.add(arr[i]);
stack.push(list);
}
}
//栈中其余剩余的元素
while (!stack.isEmpty()){
List<Integer> list=stack.pop();
int nextindex=stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
for (Integer x:list){
res[x][0]=nextindex;
res[x][1]=-1;
}
}
return res;
}