给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

    求在该柱状图中,能够勾勒出来的矩形的最大面积。

    示例 1:
    image.png

    输入:heights = [2,1,5,6,2,3]
    输出:10
    解释:最大的矩形为图中红色区域,面积为 10
    示例 2:
    image.png

    输入: heights = [2,4]
    输出: 4

    提示:

    1 <= heights.length <=105
    0 <= heights[i] <= 104


    1. class Solution {
    2. int[] stk; //定义栈
    3. int tt; //定义栈顶
    4. public int largestRectangleArea(int[] heights) {
    5. int n = heights.length;
    6. if(n == 1) return heights[0];
    7. int res = 0;
    8. int[] newHeights = new int[n+2];
    9. //添加哨兵
    10. newHeights[0] = 0;
    11. System.arraycopy(heights,0,newHeights,1,n);
    12. newHeights[n+1] = 0;
    13. heights = newHeights;
    14. n += 2;
    15. //定义栈
    16. stk = new int[n+2];
    17. for(int i = 1; i < n; ++i){
    18. while(tt > 0 && heights[stk[tt]] > heights[i]){
    19. //出栈
    20. int curHeight = heights[stk[tt--]];
    21. int left = stk[tt] + 1;
    22. int right = i - 1;
    23. res = Math.max(res,(right-left+1)*curHeight);
    24. }
    25. stk[++tt] = i;
    26. }
    27. return res;
    28. }
    29. }