---------------------
- 涉及内容：
- 单调栈
- 2020/10/25
题目如下：
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
补充知识点：
- 单调栈
单调递增栈就是从栈底到栈顶是从大到小
单调递减栈就是从栈底到栈顶是从小到大
实现：
- 解法①：单调栈，以上面的图来分析过程，从最左边柱子开始，先入栈，遇到的柱子比它矮，则说明找到了右边界，
此时需要做的时候，出栈，并且计算这个柱子的面积了，接着矮柱子入栈。接下来的两个柱子都比它高，入栈。
当下一根柱子A要入栈的时候，比上一根柱子矮，则说明找到了上一根柱子的右边界，此时将其出栈并且可以计
算该柱子的面积，然后柱子A继续和之前的柱子比较，发现上上根柱子也比它高，又找到了一个边界，将上上根
柱子出栈，并计算它到要入栈之间的面积。依次类推
-------------------------------------------------------------------------------------------------------------
- 部分说明：
- 能力有限，直接代入演算更加容易理解
- 时间复杂度：O（N）
- 空间复杂度：O（N）
-----------------------------------------------------------------------------------
C++
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxArea = 0;
stack<int> newStack;
heights.push_back(0);
for (int i = 0; i < heights.size(); ++i) {
// 如果栈不空并且如果要入栈的元素比栈内元素要小的话，则将栈内元素出栈，并计算面积
while (!newStack.empty() && heights[newStack.top()] >= heights[i]) {
int cur = newStack.top();
newStack.pop(); // 出栈
maxArea = max(maxArea, heights[cur] * (newStack.empty() ? i : (i - newStack.top() - 1))); // L1
}
newStack.push(i); // 入栈的是数组下标索引
}
return maxArea;
}
};
------------------------------------------------------------------------------------------------------------
入栈是递增方式，即左边界就是当前柱子的上一根柱子或者它本身就是第一根柱子，主要是寻找右边界
while循环流程演算，L1 部分结合图形
以(i - newStack.top() - 1)) ，当 元素3要入栈时为例
当value= 3 时，进入while循环
此时maxArea计算的是value = 3 之前比它高的柱子的矩形面积
如：maxArea = 6 * ( 4 - 2 - 1 ) = 6 ,
接着while
maxArea = 5 * ( 4 - 1 - 1 ) = 10 ,
以newStack.empty() = true 为例
当value = 1 时，进入while
此时，newStack中唯一的元素出栈
maxArea = 2 * 1
------------------------------------------------------------------------------------------------------------