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 heightint 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;} };