思路:

• 分析题意
• 找到当前柱子能够向左和向右扩的最大距离(即找到左边和右边第一个小于等于该柱子的元素)
• 注意如果左边没有小于等于该点的柱子 left[i] = -1
• 如果右边没有小于等于该点的柱子 right[i] = n
• area = (r[i] - l[i] - 1) * heights[i]
• 最后取max

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] stk = new int[n+10];
        int tt = 0;
        int[] left = new int[n];
        int[] right = new int[n];
        for(int i = 0 ; i < n ; i++){
            while(tt != 0 && heights[stk[tt]] >= heights[i])
                tt--;
            if(tt == 0)
                left[i] = -1;
            else
                left[i] = stk[tt];
            stk[++tt] = i;
        }
        while(tt != 0)
            tt--;
        for(int i = n-1 ; i>=0 ; i--){
            while(tt != 0 && heights[stk[tt]] >= heights[i])
                tt--;
            if(tt == 0)
                right[i] = n;
            else
                right[i] = stk[tt];
            stk[++tt] = i;
        }
        int ans = 0;
        for(int i = 0 ; i < n ; i++){
            ans = Math.max((right[i] - left[i] - 1)*heights[i],ans);
        }
        return ans;
    }
}