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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea (int[] heights) {
        if (heights.length == 0){
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }
        int ans = 0;
        LinkedList<Integer> list = new LinkedList<>();
        list.add(0);
        for (int i = 1; i < heights.length; i++) {
            if (heights[list.peekLast()] <= heights[i]) {
                list.addLast(i);
            } else {
                while (!list.isEmpty() && heights[list.peekLast()] > heights[i]) {
                    int temp = list.pollLast();
                    if (list.isEmpty()) {
                        ans = Math.max(ans, heights[temp] * (i - (-1) - 1));
                    } else {
                        ans = Math.max(ans, heights[temp] * (i - list.peekLast() - 1));
                    }
                }
                list.add(i);
            }
        }
        while (!list.isEmpty()) {
            int temp = list.pollLast();
            while (!list.isEmpty() && heights[temp] == heights[list.peekLast()]){
                temp = list.pollLast();
            }
            if (list.isEmpty()) {
                ans = Math.max(ans, heights[temp] * (heights.length - (-1) - 1));
            } else {
                ans = Math.max(ans, heights[temp] * (heights.length - list.peekLast() - 1));
            }
        }
        return ans;
    }
}