[LeetCode] Largest Rectangle in Histogram | 直方图最大矩形覆盖

https://leetcode.com/problems/largest-rectangle-in-histogram/#/description

再次做，还是没能第一时间写出bug-free的最佳解法。

这是一道很好的题，暴力/DP做是O(n^2)，分治（以最矮的矩形为分界点）做是O(nlogn)，单调栈则可以神奇地做到平摊O(n)。

总之要记住这个技巧，在需要找一个元素左、右边第一个比它小/大的元素时，要想到单调栈。

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        if (height.empty()) {
            return 0;
        }
        stack<int> stk;
        long long res = 0, s;
        height.push_back(-1);  // virtual height
        int left, right, h;
        for (int i = 0; i < height.size(); ++i) {
            right = i - 1;
            while (!stk.empty() && height[i] <= height[stk.top()]) {
                h = height[stk.top()]; stk.pop();
                left = stk.empty()? 0 : (stk.top()+1);
                s = (right - left + 1) * h;
                res = max(res, s);
            }
            stk.push(i);
        }
        return res;
    }
};