Preface
上篇讲了一道单调栈Hard题接雨水，这篇来讲一道很类似但细节有很大不同的Hard题柱状图中最大的矩形 - 力扣。
回忆一下上两篇的解题步骤：
- 判断这道题能否用单调栈解决
- 判断单调性，给出三板斧
- 模拟计算过程，删改模板
照例贴出单调栈模板：
// 单调栈模板，不懂可以看我的上篇文章 for (遍历这个数组) { while (栈不为空 && 栈顶元素与当前数组元素比较) { 出栈； } 入栈； } 复制代码
84. 柱状图中最大的矩形
Description
Simulation
思路分析：
- 大眼一瞧，柱状图高高低低，计算面积，这不是接雨水吗？单调栈确认！
- 判断单调性？可以看到图中都是遇到小值需要出栈的时候才计算面积，可以确认是递增的栈，也就是栈顶元素最大。单调性确定！直接三板斧给出：
- 单调栈存入下标计算宽度，根据出栈的最小值计算高度（具体思路上篇文章已经详细给出，在此不赘述）删改后可得：
for (int i = 0; i < h.size(); i++) { while (!stk.empty() && h[i] < h[stk.top()]) { // 出栈条件 int pre = stk.top(); // 保存要出栈的元素 stk.pop(); if (!stk.empty()) { // 计算面积 int height = h[pre]; int width = i - stk.top() - 1; res = max(res, height*width); // 保留更大的值 } } stk.push(i); } 复制代码
但这样就足够了吗？显然不行，设想两种情况：
- 输入两个元素[2,5]，本身递增可以直接入栈，没有出栈怎么计算面积？
- 输入任意一个元素，怎么计算面积？
其实解决方法很简单，我们只要在数组前后各加一个0就可以了。0一定是最小元素，在前面加一个0不用担心栈空的情况，每次出栈都计算一下面积；没有出栈条件就创造出栈条件，所以在数组后面加一个0。
h.insert(h.begin(), 0); // 前插一个0 h.push_back(0); // 后插一个0 复制代码
Solution
完整代码如下：
class Solution { public: int largestRectangleArea(vector<int>& h) { stack<int> stk; int res = 0; h.insert(h.begin(), 0); h.push_back(0); for (int i = 0; i < h.size(); i++) { while (!stk.empty() && h[i] < h[stk.top()]) { // 出栈条件 int pre = stk.top(); // 保存要出栈的元素 stk.pop(); // 栈不会空 int height = h[pre]; int width = i - stk.top() - 1; res = max(res, height*width); // 保留更大的值 } stk.push(i); } return res; } }; 复制代码
Conclusion
可以看到这道题跟接雨水虽然相似，但麻烦了许多，特殊值的输入给我们的解题思路带来了一定困扰，不过你不能指望Hard题都是套个模板就能AC的。
虽然三板斧很好用，但一些特殊条件的计算仍然是需要你自己的判断，那么问题来了：怎么提高自己的能力？
刷题！刷题！还是TMD刷题！！！🍗🍗
