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; } }; 复制代码
Conclusion
总结一下单调栈的分析思路：
- 一般来说，题目中要求找到一个元素左边（右边）第一个比自己大（小）的元素，我们应该首先想到单调栈。它的应用范围可以说是很窄，但缺点也是优点，题目类型很好辨认。
- 分析时应该首先分析单调性，判断单调减还是单调增，直接写出模板。
- 在模板的基础上进行删改，计算题目要求。
