Monotonic stack structure

What is a monotonous stack ?

A specially designed stack structure , In order to solve the following problems ：

Given an array that may contain duplicate values arr,i The number of positions must have the following two information

1. arr[i] The left side of the is away from i Recent and less than ( Or greater than )arr[i] Where is the number of ?
2. arr[i] The right side of the is away from i Recent and less than ( Or greater than )arr[i] Where is the number of ?
   If you want arr Two messages for all locations in , How to make the process of getting information as fast as possible .
   So how to design it ?

The required time complexity is 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  looking for him for thousand times in the crowd , Suddenly look back , The man was in the dim light . */
public class Code01_MonotonousStack {
    
    /* arr=[ 3, 1, 2, 3] index 0 1 2 3  return （ Record position , No, just remember -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];
        //  Only subscripts are stored in the monotone stack 
        Stack<Integer> stack=new Stack<>();
        //  Traversal array arr Every number in the 
        for(int i=0; i<arr.length; i++){
    
            while(!stack.isEmpty() && arr[stack.peek()]>arr[i]){
    //  When the current number can't fall 
                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 the number at this time is equal to the number at the top of the stack , Add directly to the list at the top of the stack 
            //  If it's less than , Create a new list by yourself , Put it in the stack 
            if(!stack.isEmpty() && arr[stack.peek().get(0)]==arr[i]){
    
                stack.peek().add(Integer.valueOf(i));
            }else{
    
                /*  Why ArrayList without LinkedList? ArrayList Compare the value of the last position LinkedList fast  LinkedList You need to go through it all （ however LinkedList Yes getLast() Method ） */
                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;
    }

    //  Violent solution 
    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");
    }
}