这个模板有些复杂 已经不用了

Java 直方图中最大的矩形 题解 + 单调栈模板

使用模板中含重复元素的单调栈 类似 [1 3 3 3 1] 这样的数组 中间3个3得到的左右边界都是一样的 左边界都是是index = 0 右边界都是 index = 4 所以 3 * (4 - 0 - 1 ) 答案显然

样例

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class MonoStack {
    // 左边离我最近的比我小的  右边离我最近的比我小的 (等于不算）  单调栈中存储的数组中的下标  栈底到顶由小到大
    //  这种单调栈相比而言设计的更巧妙  只需要比较一次

    public static int[][] getNearLessNoRepeat(int[] arr) {
        int[][] res = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >arr[i]) {
                int popIndex = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                res[popIndex][0] = leftLessIndex;
                res[popIndex][1] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int popIndex = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = -1;
        }
        return res;
    }

    // 可以处理重复元素 进栈的是list
    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集合
                List<Integer> popIs = stack.pop();
                // 取位于下面位置的列表中，最晚加入的那个
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                // popi是数组下标
                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)); //  将下标压在一起  因为栈中的每一个元素都是list 把下标压倒已经有的那个相等的栈顶的list中
            } else {
                // 当栈顶元素小于当前数
                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;              // 右边没有
                res[popi][1] = arr.length;    
            }
        }
        return res;
    }
/*****************************************************************************/


    public static void main(String[] args) {
        int[] a = {4,1000,1000,1000,1000};
        int[][] res = getNearLess(a);
        for(int i = 0 ; i < res.length ; i++) {
            for(int j = 0 ; j < res[0].length ; j++) {
                System.out.print(res[i][j] + " ");
            }
            System.out.println();
        }
        int max = 0;
        for( int i = 0 ; i < res.length ; i++) {
            max = Math.max(max,a[i]*(res[i][1] - res[i][0] - 1));
        }
        System.out.print(max);
    }
}