思路分析
非常经典的思路题，主要利用了单调栈的性质和贪心的思想来简化问题，从而得到了O(n)复杂度的算法。核心思想大致是这样：考虑如果矩形序列的高度是非降的，那么我们只需要顺序将其入栈，然后再遍历弹出一遍，即可维护一个最大值，得到答案。具体的计算过程是：从栈顶元素开始遍历，不断地将前面高度低的元素出栈，计算它与右边最高的矩形所组成的面积，并记录最大值。而在输入序列任意的情况下，我们可以尝试在遍历序列的过程中去维护一个单调栈，其中存储的是一个单调递增序列的下标。如果一个新的矩形的高度大于当前栈顶，则可以将其加入单调栈中保持栈的性质不变；否则，就要对栈进行更新操作。
算法的核心，就在于如何更新单调栈，使得它既可以继续保持单调性质，并且也能够在更新的过程中尝试计算最大有效面积。由于栈是单调的，这就意味着其中可能存在某个元素，在它以前的元素都比新矩形要小；但也可能不存在这样的元素，也就意味着整个栈中的矩形均大于新矩形。对于前一种情况，我们可以将新矩形，与第一个小于等于新矩形的矩形之间的元素全部出栈，并在出栈的过程中记录产生的最大面积——根据下标和矩形高度，这是显然可求的；然后我们再将新的矩形入栈，这样就保持了栈的单调性质。这个过程使得我们清除了单调栈中的一部分大于新矩形的单调递增元素，并加入了一个新的矩形，而且维持了栈的单调性。此时我们注意到单调栈的一个性质：它其中的元素，虽然在位置上是不连续的，但是两个不连续的矩形之间所夹着的矩形，高度一定是高于这两个矩形的！这也就意味着在单调栈的出栈过程中所得到的最大值，也一定是这段矩形所围面积的最大值。对于后一种情况，我们直接出栈所有元素，并在这个过程中同样记录产生的最大面积，最后将新矩形入栈，过程结束后栈中就只有一个元素。
上述的更新维护过程保持了栈的单调性，下面的重点就是，如何确保更新过程中能够记录到所有可能出现的最大值呢？考虑我们每次遍历到右端一个新的矩形，这个矩形与先前所有矩形中的一个，一定可以组成一个当前的最大面积。如果我们尝试遍历一遍先前所有矩形求一个最大面积，那么算法就成了O(n^2)复杂度。考虑与新矩形配对的矩形，有且只有两种情况：要么存在于单调栈中比它大的那部分矩形中，要么存在于单调栈中小于它的那部分矩形中——换句话说就是比它大或者比它小。我们首先考虑后一种情况，在这种情况下，新矩形与小于它的元素组成了新的单调栈，这个栈必然将在未来的某个时刻被清空，过程中一定可以得到一个最大值；也有可能前面找不到比这个矩形更小的元素了，这样的话围成面积的长度就要从最开头开始算起。对于后一种情况，我们画图模拟一下，会发现这个面积一定是新矩形与大于它的最小矩形所围成的面积，而这个面积也显然会被计算到，包含在了出栈的过程中。再次重复一遍，单调栈中如何出栈呢？固定栈顶矩形高度和位置不变，不断出栈比它低的矩形，围成的面积就是矮矩形与高矩形位置差，乘以矮矩形的高度。
最后，如何保证遍历完成后单调栈一定被清空呢？很简单，直接在末尾添加一个高度为零的矩形即可。
代码
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
height.push_back(0);
stack<int> stk;
int res = 0;
rep(i, height.size()) {
if ( stk.empty() || height[i] >= height[stk.top()] ) {
stk.push(i);
} else {
int idx = -1;
while ( !stk.empty() && height[stk.top()] > height[i] ) {
idx = stk.top(); stk.pop();
res = max(height[idx] * (stk.empty() ? i : i - stk.top() - 1), res);
}
stk.push(i);
}
}
return res;
}
};