Preface

继上篇【面试高频】详解单调栈，今天我们来讲述一下如何用我给出的单调栈模板刷题。

所谓单调栈其实就是栈内元素具有单调性，常用于解决下一个更大元素 这种问题。

我们会讲一下其中最具代表性的三道题，其中一道Medium，两道Hard，保证你看完一定有所收获：

 // 单调栈模板，如果不懂可以看我的上篇文章
 for (遍历这个数组) {
     while (栈不为空 && 栈顶元素与当前数组元素比较) {
         出栈；
     }
     入栈； 
 }

739. 每日温度

Description

Simulation

思路：我们先列一个表格分析一下示例数据是怎么来的

	第1天	第2天	第3天	第4天	第5天	第6天	第7天	第8天
温度	73	74	75	71	69	72	76	73
下一个更高的温度	第2天	第3天	第7天	第6天	第6天	第7天	无	无
天数差	1	1	4	2	1	1	0	0

首先想到的当然是暴力解法，两层 for 循环挨个遍历一遍，计算天数差即可，时间复杂度O(n^2)。

get到暴力解法也很重要，毕竟不是什么时候都能想到最优解，而且我们还可以基于暴力解法进行下一步优化。

题目中要求计算下一个更高的温度的天数差，其实就是要找到自己右边第一个比自己大的元素，然后计算下标之差。

很明显要用到一个单调减（栈头元素最小）的栈，通过O(n)的时间复杂度（即遍历一遍）就能找到每个元素的右边第一个比它大的元素，本质就是空间换时间。

为什么是单调减？

答：因为只有递减的时候，我们才能得到天数差，如74放入栈时，73即可出栈，第一天的天数差就得到了。
怎么计算天数差？

答：单调栈内只存放元素的下标即可，需要数值比较时直接使用 t[i] 即可。
模板怎么用？?

既然已经分析出要用单调栈，我们可以直接把三板斧（模板）使出来：

 // 模板
 stack<int> stk;
 for (int i = 0; i < t.size(); i++) {                // 遍历温度数组t
     while (!stk.empty() && t[i] > t[stk.top()]) {   // 出栈条件，保持单调减
         stk.pop();
     }
     stk.push(i);                                    // 入栈，放入下标
 }

在脑中模拟一下出入栈的过程：

栈为空，73的下标0入栈，栈内元素 0
74 > 73，73出栈74入栈，天数差为1，栈内元素 1
75 > 74，74出栈75入栈，天数差为1，栈内元素 2

从第二步就可以看出来，我们需要在栈内元素出栈前通过下标计算天数差，增加一行即可：

     while (!stk.empty() && t[i] > t[stk.top()]) {   // 出栈条件，保持单调减
         res[stk.top()] = i - stk.top();    // 添加计算
         
         stk.pop();
     }

Solution

完整代码如下，可以尝试一下，原题链接：

 // hrh 8/28 
 class Solution {
 public:
     vector<int> dailyTemperatures(vector<int>& t) {
         vector<int> res(t.size());
         stack<int> stk;     
 ?
         for (int i = 0; i < t.size(); i++) {                // 遍历
             while (!stk.empty() && t[i] > t[stk.top()]) {   // 出栈条件
                 res[stk.top()] = i - stk.top();             // 计算天数差值
                 stk.pop();                                  // 保持单调减
             }
             stk.push(i);                                    // 入栈
         }
 ?
         return res;
     }
 };

总结一下解题过程：

判断这道题能否用单调栈解决
判断单调性，给出三板斧
模拟计算过程，删改模板得到结果

42. 接雨水

Description

Simulation

思路：

看图分析，只有下一个大于等于自己的元素插入才会形成凹槽接到雨水。所以显而易见，我们应该使用单调栈。
单调性怎么判断？很明显，比自己小的可以直接插入，大的插入要让前面的小元素出栈，因此我们需要一个递减的栈（栈顶元素最小）。
面积怎么计算？底 ? 高大伙都知道，然后按行计算，下面是分析：

首先明确一下单调栈里到底要存什么内容，每个柱的高度？不不不！我们需要下标来计算宽度，而下标又可以直接get到对应的高度，所以只需一个单调栈来存储下标就可以了。

画了一张图进行模拟计算过程，一组数[2,1,0,3] 从左到右依次入栈：

2入栈，栈为空，下标i直接入栈，栈内元素 i 。
1<2，直接入栈，栈内元素 i, i+1 。
0<1，直接入栈，栈内元素 i, i+1, i+2 。
3>0，保存0作为基底然后出栈，计算凹槽面积：高为1，选择3与当前栈顶元素1之间小的那个（木桶理论，看短的）；底为1，3的下标减去1的下标 (i+3) - (i+2) ；总面积+1，继续判断 👇
3>1，保存1作为基底然后出栈，计算凹槽面积：高为1，因为1作为基底，此时栈顶元素为2，所以高为 2-1=1 ，下标计算出底为2；总面积+2，继续判断 👇
3>2，2出栈，但此时栈为空，不需要继续计算。3终于入栈，最后栈内元素 i+3。
总面积为3

看完模拟过程，相信你已经有了思路，单调减的栈，三板斧一整，我们只需要在出栈的时候计算面积即可。下面给出完整代码 🍉🍉🍉

Solution

 // hrh 8/29 
 class Solution {
 public:
     int trap(vector<int>& h) {
         stack<int> stk;    
         int res = 0;
         
         // 三板斧！
         for (int i = 0; i < h.size(); i++) {
             while (!stk.empty() && h[i] >= h[stk.top()]) {
                 int base = h[stk.top()];        // 保存基底然后出栈
                 stk.pop();      
                 
                 // 栈不空时计算面积
                 if (!stk.empty()) {             
                     int height = min(h[stk.top()], h[i]) - base;
                     int width = i - stk.top() - 1;
                     res += height*width;
                 }
             }
             
             stk.push(i);
         }
 ?
         return res;
     }
 };

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

};