给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

解题思路：暴力 / 单调栈

首先我们分析一下，【第 i 列】柱子可以勾勒出来的矩形最大面积为？（0 ≤ i ＜ n）
无外乎就是往左右两边延申，能延伸多少延申多少，直到碰到比它矮的柱子无法继续延伸为止。
——当出现凸的时候！也就是柱子的左边第一次出现比它低的，右边也出现第一次比它低的时候，无法再继续延申！

1、解法一：暴力

● 遍历第 i 列，需要一层for循环——
 ● 分别找到左边第一个比它矮的，右边第一个比它矮的，需要两层并列的for循环——，嵌套后时间复杂度为
 ● 计算当前柱子可以勾勒得最大矩形面积

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 找凸，即对于每一个柱子(凸的制高点)来说，需要找到左右两遍第一个比它小（左右制低点）的下标（在这个区间中就是它能扩展的最大面积）
        int result = 0;
        for(int i=0; i<heights.length; i++){
            // 找左边制低点
            int j = i-1;
            for(; j>=0; j--){
                if(heights[j] < heights[i]) break;
            }
            int leftLowIndex = j;
            // 找右边制低点
            j = i+1;
            for(; j <heights.length; j++){
                if(heights[j] < heights[i]) break;
            }
            int rightLowIndex = j;

            // 计算下标 i 柱子的最大扩展面积
            result = Math.max(result, (rightLowIndex - leftLowIndex - 1) * heights[i]);
        }
        return result;
    }
}

本题可不可以像42.接雨水一样对暴力做优化呢？
即：提前构造左数组、右数组，需要的时候直接取。——可以是可以，但是时间复杂度并不会提升（接雨水中是优化了一个数量级），本质上构造左右数组的时候，仍需要两个并列的，没啥本质区别，反而还增加了空间，所以没必要去做。

2、单调栈

● 什么时候要想到用单调栈？
——通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素！

在这道题中，我们要寻找凸点，即找当前柱子中，左边第一次出现比它低的柱子，以及右边第一次出现比它低的柱子，应该要能够想到借助单调栈求解。

● 凸的寻找
——如果我们知道了凸点（低高低）在两处制低点的下标，那么我们就可以求当前柱子能够延申出的最大矩形。

遍历第 i 列时，我们维护一个单调非递减的栈（保存下标）：——1层for循环，时间复杂度
● 如果第 i 列（当前柱子）高度 ≥ 栈顶，直接压入当前柱子的下标 i
● 如果第 i 列（当前柱子）高度 ＜ 栈顶，那么就有可能形成凸点（heights[i] 可以理解为：栈顶这个柱子右边第一次比它低的柱子）。
 弹出栈顶元素top（凸的制高点，此时求解的就是栈顶这个柱子的矩形面积）后，再取一次栈顶元素left（如果存在，那么就是凸点另一侧制低点，即当前柱子左边第一次比它低的柱子位置），计算这个凸中（top）的矩形面积 = (i - left - 1) * heights[top]。最后将 i 压入栈，因为它可能构成下一个凸点。

⭕ 注意：和47. 接雨水类似的，第 0 个柱子和最后一个柱子要特别关注！
(1) 47. 接雨水中：这两处是无法蓄水的。
(2) 本题中：这两处却是可以勾勒矩形的！但是无法构成凸点，所以我们要手动构造，即在heights数组中首、尾再添加一个制低点！具体实现：[-1, heights[0], heights[1], ..., heights[len-1], -1]

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 手动构造两个制低点
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = -1;
        newHeights[newHeights.length - 1] = -1;
        for(int i=1; i<newHeights.length-1; i++){
            newHeights[i] = heights[i-1];
        }

        int result = 0;
        LinkedList<Integer> stack = new LinkedList<>();
        for(int i=0; i<newHeights.length; i++){
            if(stack.isEmpty() || newHeights[stack.getLast()] <= newHeights[i]) stack.addLast(i);
            else{
                while(!stack.isEmpty() && newHeights[stack.getLast()] > newHeights[i]){
                    int curIndex = stack.removeLast();
                    if(!stack.isEmpty()){
                        result = Math.max(result, (i - stack.getLast() - 1) * newHeights[curIndex]);
                    }
                }
                stack.addLast(i);
            }
        }
        return result;
    }
}