84. 柱状图中最大的矩形

输入: [2,1,5,6,2,3]
输出: 10

 public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int res = 0;
        //单调递增保存索引的栈
        Stack<Integer> stack = new Stack<Integer>();
        //遍历数组
        for (int i = 0; i < heights.length; i++) {
            //栈不为空并且遍历到的元素值小于栈中保存的索引对应元素值，需要出栈计算面积
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                //出栈保存索引
                int cur = stack.pop();
                //计算出栈索引左边的索引，栈空赋值为-1
                int left = stack.isEmpty() ? -1 : stack.peek();
                //第一个出栈索引右边的索引减去出栈索引左边的索引再-1计算出长度*出栈索引对应元素值计算面积，取最大
                res = Math.max(res, (i - left - 1) * heights[cur]);
            }
            //单调递增的话，直接入栈
            stack.push(i);
        }
        //同上
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            int left = stack.isEmpty() ? -1 : stack.peek();
            res = Math.max(res, (heights.length - left - 1) * heights[cur]);
        }
        return res;
    }