单调栈解决Next Greater Number一类题

单调栈是什么？

单调栈使得每次新元素入栈后，栈内元素都保持有序（单调递增或者单调递减）。 单调递增栈：栈中数据出栈的序列为单调递增序列。 单调递减栈：栈中数据出栈的序列为单调递减序列。 注意：这里所说的递增递减是出栈的顺序，不是栈中数据的顺序。

单调栈的应用

通过使用单调栈，可以访问到下一个比它大（小）的元素。也就是说在队列或数组中，我们需要通过比较前后元素的大小关系来解决问题时，需要使用单调栈。

例如，给一个数组[2, 1, 2, 4, 3]，返回每个元素后面第一个比它自身大的数，如果没有就返回-1。 第一个元素2，其后面的第一个比它自身大的元素是4； 第二个元素1，其后面的第一个比它自身大的元素是2； 第三个元素2，其后面的第一个比它自身大的元素是4； 第四个元素4，其后面没有比它自身大的元素，所以返回-1； 第五个元素3，其后面没有元素了，所以返回-1。 所以最后返回的数组是[4, 2, 4, -1, -1]。

这个问题可以这样抽象：把数组的元想象成并列站立的人，元素大小是人的身高。这些人面对你站成一列，（注意是一列，不是一排）。如何求元素2的Next Greater Number呢？很简单，如果能够看到元素2，那么它后面可见的第一个人就是2的Next Greater Number，因此比2小的身高不够，都被2挡住了，第一个露出来的就是答案。如下图所示。 代码如下：

vector<int> nextGreaterElement(vector<int>& nums){ vector<int> res(nums.size()); //存放答案的数组 stack<int> s; int size = nums.size() - 1; for(int i = size; i >= 0; i--){ //倒着往栈里面放 while(!s.empty() && s.top() <= nums[i]) //判断格子高矮 s.pop(); //矮个子起开，反正都是被挡住的 res[i] = s.empty() ? -1 : s.top(); //这个元素身后第一个高个子 s.push(nums[i]); //进栈，接受后面的身高判定 } }

这就是单调栈解决问题的模板。for循环要从后往前遍历元素，因为我们借助的是栈结构，倒着入栈，其实就是正着出栈。 while循环是把两个高个子元素之间的元素排除，因为它们的存在没有意义，前面挡着个更高的元素，所以它们不可能被作为后续进来的元素的Next Greater Number了。

伪代码如下：

stack<int> s; for i : len{ while(栈不空 && 栈顶元素小于当前元素){ 栈顶元素出栈； } 更新结果； 当前元素入栈； }

LeetCode496.下一个更大元素 I

先忽略数组nums1，先对nums2中的每一个元素，求出其下一个更大的元素。随后对于将这些答案放入哈希映射（hashmap）中，再遍历数组nums1，并直接找出答案。对于nums2，就可以使用单调栈来解决这个问题。如下图所示： 然后遍历nums1的中元素，在hashmap中找其映射值即可。 代码如下：

class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { map<int, int> numMap; stack<int> s; vector<int> res; if(nums1.size() == 0 || nums2.size() == 0) return res; int size = nums2.size()-1; for(int i = size; i >= 0 ; i--){ //倒着入栈，就可以正着出栈 while(!s.empty() && nums2[i] > s.top()) //while循环是将两个“高个”元素之间的元素排除，因为它们的存在没有意义 s.pop(); int temp = s.empty()? -1 : s.top(); numMap.insert(make_pair(nums2[i], temp)); s.push(nums2[i]); } for(int i = 0; i < nums1.size(); i++){ res.push_back(numMap[nums1[i]]); } return res; } };

LeetCode503.下一个更大元素 II

这题和上一题的区别是：输入为单数组，并且还是一个循环数组。

首先，计算机的内存都是线性的，没有真正意义上的环形数组，但是我们可以模拟出环形数组的效果，一般是通过%（求余），获得环形特效。

还是使用单调栈来解决，直接套用模板，但是由于输入为循环数组，所以遍历数组两次，每次pop之前都去更新一下res，因为数组有可能出现重复元素。

//pop之前，先更新res if(res[s.top()] == -1) res[s.top()] = s.empty() ? -1 : nums[i % size];

代码如下：

class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { if(nums.size() == 0) return {}; vector<int> res(nums.size(), -1); stack<int> s; int size = nums.size(); for(int i = 0; i < size*2; i++){ while(!s.empty() && nums[s.top()] < nums[i % size]){ if(res[s.top()] == -1) res[s.top()] = s.empty() ? -1 : nums[i % size]; s.pop(); } s.push(i % size); } return res; } };

LeetCode739.每日温度

第一天73摄氏度，第二天74摄氏度，比73大，所以对于第一天而言，只要等1天就能等到一个更暖和的气温； 第三天75华氏度比第二天74华氏度大，所以也是等1天； 第三天75华氏度，要等到4天后，达到76华氏度，才能更暖和； 后面的同理。

这个问题本质上也是找Next Greater Number，只不过是现在不是问你Next Greater Number是多少，而是问你当前距离Next Greater Number的距离是多少。

代码如下：

class Solution { public: vector<int> dailyTemperatures(vector<int>& T) { if(T.size() == 0) return {}; vector<int> res(T.size()); stack<int> s; //这里放元素索引，而不是元素 int size = T.size()-1; for(int i = size; i >= 0; i--){ while(!s.empty() && T[s.top()] <= T[i]) s.pop(); res[i] = s.empty()? 0 : s.top()-i; //得到索引间距 s.push(i); //加入索引，而不是元素 } return res; } };

后续还有相关的题再补充总结。 如有问题，欢迎大家指正！