单调栈是什么?
一种特别设计的栈结构,为了解决如下的问题:
给定一个可能含有重复值的数组arr,i位置的数一定存在如下两个信息
1) arr[i] 的左侧离 i 最近并且小于(或者大于)arr[i]的数在哪?
2) arr[i] 的右侧离 i 最近并且小于(或者大于)arr[i]的数在哪?
如果想得到arr中所有位置的两个信息,怎么能让得到信息的过程尽量快。
那么到底怎么设计呢?
要求时间复杂度为O(N)
package com.harrison.class14;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* @author Harrison
* @create 2022-03-26-19:03
* @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。
*/
public class Code01_MonotonousStack {
/*
arr=[ 3, 1, 2, 3]
index 0 1 2 3
返回(记位置,没有就记-1):
[
0:[-1, 1]
1:[-1, -1]
2:[1, -1]
3:[2, -1]
]
*/
public static int[][] getNearLessNoRepeat(int[] arr){
int[][] res=new int[arr.length][2];
// 单调栈里只存下标
Stack<Integer> stack=new Stack<>();
// 遍历数组arr里的每一个数
for(int i=0; i<arr.length; i++){
while(!stack.isEmpty() && arr[stack.peek()]>arr[i]){
int j=stack.pop();
int leftLessIndex=stack.isEmpty()?-1:stack.peek();
res[j][0]=leftLessIndex;
res[j][1]=i;
}
stack.push(i);
}
while(!stack.isEmpty()){
int j=stack.pop();
int leftLessIndex=stack.isEmpty()?-1:stack.peek();
res[j][0]=leftLessIndex;
res[j][1]=-1;
}
return res;
}
public static int[][] getNearLess(int[] arr){
int[][] res=new int[arr.length][2];
Stack<List<Integer>> stack=new Stack<>();
for(int i=0; i<arr.length; 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而不用LinkedList?
ArrayList拿最后一个位置的值比LinkedList快
LinkedList需要全部遍历一遍(但是LinkedList有getLast()方法)
*/
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;
}
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;
}
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;
}
// 暴力解
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;
}
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] || res2[i][1]!=res2[i][1]){
return false;
}
}
return true;
}
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=200000;
System.out.println("test begin");
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;
}
}
System.out.println("test finish");
}
}