题解 | #直方图内最大矩形#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea(int[] heights) {
        // write code here
        int[] leftMinIndexs = new int[heights.length];
        int[] rightMinIndexs = new int[heights.length];
        Stack<ArrayList<Integer>> stack = new Stack<>();
        for (int i = 0; i < heights.length; i++) {
            int currentNumber = heights[i];
            while (!stack.isEmpty() && heights[stack.peek().get(0)] > currentNumber) {
                ArrayList<Integer> tmpArr = stack.pop();
                for (int tmpNum : tmpArr) {
                    if (stack.isEmpty()) {
                        leftMinIndexs[tmpNum] = -1;
                    } else {
                        leftMinIndexs[tmpNum] = stack.peek().get(stack.peek().size() - 1);
                    }
                    rightMinIndexs[tmpNum] = i;
                }
            }
            if (!stack.isEmpty() && heights[stack.peek().get(0)] == currentNumber) {
                ArrayList<Integer> tmpArr = stack.peek();
                tmpArr.add(i);
                continue;
            }
            ArrayList<Integer> currentArr = new ArrayList<>();
            currentArr.add(i);
            stack.push(currentArr);
        }
        while (!stack.isEmpty()) {
            ArrayList<Integer> tmpArr = stack.pop();
            for (int tmpNum : tmpArr) {
                if (stack.isEmpty()) {
                    leftMinIndexs[tmpNum] = -1;
                } else {
                    leftMinIndexs[tmpNum] = stack.peek().get(stack.peek().size() - 1);
                }
                rightMinIndexs[tmpNum] = heights.length;
            }
        }
        int ans = 0;
        for (int i = 0; i < rightMinIndexs.length; i++) {
            int currentlefttMinIndex = leftMinIndexs[i];
            int currentrightMinIndex = rightMinIndexs[i];
            int currentSquare = heights[i] * (currentrightMinIndex - currentlefttMinIndex - 1);
            ans = Math.max(ans, currentSquare);
        }
        return ans;
    }
}