直方图中的最大矩形

单调栈的最典型用法，下面的代码可以作为单调栈的模版进行记忆：

• 注意其中第18行在数组最后添加了一个0，这么做可以保证遍历最后一个元素时栈被清空，大大简化了代码

//
// Created by jt on 2020/9/24.
//
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    /**
     *
     * @param height int整型vector
     * @return int整型
     */
    int largestRectangleArea(vector<int>& height) {
        // write code here
        stack<int> stk;
        height.push_back(0);  // 简化代码，确保栈最后会被清空
        int maxVal = 0;
        for (int i = 0; i < height.size(); ++i) {
            while (!stk.empty() && height[i] < height[stk.top()]) {
                int h = height[stk.top()]; stk.pop();
                int leftIdx = stk.empty() ? -1 : stk.top();
                int w = i - leftIdx - 1;
                maxVal = max(maxVal, h * w);
            }
            stk.push(i);
        }
        return maxVal;
    }
};