题目
分析
这道题有两种解题思路：一种是书上的“悬线”法，一种是本题的“单调栈”法。本处只分析“单调栈”法。
先看样本数据：
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | R | F | F | F | F | F |
| 2 | F | F | F | F | F | F |
| 3 | R | R | R | F | F | F |
| 4 | F | F | F | F | F | F |
| 5 | F | F | F | F | F | F |
显然，斜体部分显示的F构成最大的一个矩形，面积是3*5=15（答案是45）。
矩形的高度
矩形的面积由高度和宽度决定。高度是比较容易确定的。
一般而言，对于位于
(i, j)处的格子，如果它是R，那么就是0——我们可以将其理解为一堵墙，高度的计算到此为止；如果它是F，那么就是它上方那个格子（(i-1, j)）的高度加1。
因此，对于样本数据，我们可以得到如下的高度结果，用heights[i][j]来记录：
0 1 1 1 1 1
1 2 2 2 2 2
0 0 0 3 3 3
1 1 1 4 4 4
2 2 2 5 5 5 矩形的宽度和单调栈
对于某个(i, j)的格子来说，还需要知道它能覆盖的宽度，而宽度是由这个格子的“高度”向左能到哪一列、向右能到哪一列决定的。我们以找左边界进行说明。
直觉的解法是，对于某一列j，依次看它左边的列（j-1, j-2, ...）的高度，一旦某列（比如说是第k列）的高度低于j的高度，那么对于j列来说，它的这个高度只能延伸到k+1列。但这个算法是\(O(n^2)\)的。
让我们引入单调栈。
这里有一篇文章讲述了基本概念。我们这里用了“单调递增栈”。考虑如下的一种情形。
假定某一行各列的高度为[3, 1, 4, 2, 5]。
- 对于
0列：它的左边界当然是自己。此时栈需要保存位置0（对应高度3）。 - 对于
1列：它的高度是1<3（当前栈顶索引0对应的高度）。这时，栈中的3毫无意义，因为对于列1来说，它的高度只有1，不可能向左拓展而构成一个高度3的矩形。所以应该弹出3，而将位置1压入（对应高度1），也就是说，第1列的高度1目前决定了右边所有列的左边界。 - 对于
2列：它的高度是4>1（当前栈顶对应的高度）。此时，位置2是有意义的，因为对于列2来说，它的高度（4）比位置1的高度（1）大，它完全可以作为后续右边各列的左边界。 - ...以此类推。
最后得到的栈只有三个元素：
| 栈 | 0 | 1 | 2 |
|---|---|---|---|
| 代表位置 | 1 | 3 | 4 |
| 代表高度 | 1 | 2 | 5 |
单调（递增）栈的特点也由此出现：它保留的位置是递增的，而且位置代表的高度也是递增的。
推导右边界与此类似，但要从最右边开始。
如下给出计算左边界的代码。需要注意的是，对于每一行，我们都要对每一列计算左右边界。
stack<int> s;
vector<int> left(m, 0), right(m, m);
// 计算左边界
for (int j = 0; j < m; ++j) {
while (!s.empty() && heights[i][s.top()] >= heights[i][j]) {
s.pop();
}
left[j] = s.empty() ? 0 : s.top() + 1;
s.push(j);
}面积的计算
对于某一行的某一列，我们已经知道了高度和该列能拓展到的左右边界，面积就很容易计算了。
答案
思考
这个方法还会在后续题目中出现，需要牢牢掌握。
按照书上的讲法，单调栈可以解决求“以某个值为最值的最大区间”等问题。