【LeetCode热题100】【栈】柱状图中最大的矩形

题目链接：84. 柱状图中最大的矩形 - 力扣（LeetCode）

要找最大的矩形就是要找以每根柱子为高度往两边延申的边界，要作为柱子的边界就必须高度不能低于该柱子，否则矩形无法同高，也就是需要找出以每根柱子为高、往两边找更低的柱子作为当前矩形的边界（不含）

可以用一个单调递增栈，存储下标，一直记录更高的柱子，一旦碰到低的柱子，此时栈顶可作为矩形的高，当前柱子作为右边界（不含），栈顶往下一个元素可作为左边界（不含），计算完成后弹出栈顶，这样可以以每个柱子的高度为矩形的高计算一次面积，且边界都是尽可能延申的

class Solution {
public:int largestRectangleArea(vector<int> &heights) {int ans = 0;heights.insert(heights.begin(), 0); // 尾哨兵heights.push_back(0); // 头哨兵stack<int> plus; // 单调递增栈for (int i = 0; i < heights.size(); i++) {while (!plus.empty() && heights[i] < heights[plus.top()]) { // 找到更低的了，说明找到边界int height = heights[plus.top()];plus.pop();ans = max(ans, height * (i - plus.top() - 1));}plus.push(i);}return ans;}
};