给定 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. }