单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

本文就通过几道算法题来看看单调栈模板的使用。

单调栈模板

首先，看一下 Next Greater Number 的原始问题，这是力扣第 496 题「下一个更大元素 I」：

给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。

函数签名如下：

  1. vector<int> nextGreaterElement(vector<int>& nums);

比如说，输入一个数组nums = [2,1,2,4,3]，你返回数组[4,2,4,-1,-1]。

解释：第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。

这道题的暴力解法很好想到，就是对每个元素后面都进行扫描，找到第一个更大的元素就行了。但是暴力解法的时间复杂度是O(n^2)。

这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。

单调栈 - 图1

这个情景很好理解吧？带着这个抽象的情景，先来看下代码。

  1. vector<int> nextGreaterElement(vector<int>& nums) {
  2.     vector<int> res(nums.size()); // 存放答案的数组
  3.     stack<int> s;
  4.     // 倒着往栈里放
  5.     for (int i = nums.size() - 1; i >= 0; i--) {
  6.         // 判定个子高矮
  7.         while (!s.empty() && s.top() <= nums[i]) {
  8.             // 矮个起开，反正也被挡着了。。。
  9.             s.pop();
  10.         }
  11.         // nums[i] 身后的 next great number
  12.         res[i] = s.empty() ? -1 : s.top();
  13.         // 
  14.         s.push(nums[i]);
  15.     }
  16.     return res;
  17. }

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

这个算法的时间复杂度不是那么直观，如果你看到 for 循环嵌套 while 循环，可能认为这个算法的复杂度也是O(n^2)，但是实际上这个算法的复杂度只有O(n)。

分析它的时间复杂度，要从整体来看：总共有n个元素，每个元素都被push入栈了一次，而最多会被pop一次，没有任何冗余操作。所以总的计算规模是和元素规模n成正比的，也就是O(n)的复杂度。

问题变形

单调栈的使用技巧差不多了，来一个简单的变形，力扣第 1118 题「一月有多少天」：

给你一个数组T，这个数组存放的是近几天的天气气温，你返回一个等长的数组，计算：对于每一天，你还要至少等多少天才能等到一个更暖和的气温；如果等不到那一天，填 0。

函数签名如下：

  1. vector<int> dailyTemperatures(vector<int>& T);

比如说给你输入T = [73,74,75,71,69,76]，你返回[1,1,3,2,1,0]。

解释：第一天 73 华氏度，第二天 74 华氏度，比 73 大，所以对于第一天，只要等一天就能等到一个更暖和的气温，后面的同理。

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

相同的思路，直接调用单调栈的算法模板，稍作改动就可以，直接上代码吧：

  1. vector<int> dailyTemperatures(vector<int>& T) {
  2.     vector<int> res(T.size());
  3.     // 这里放元素索引，而不是元素
  4.     stack<int> s; 
  5.     /* 单调栈模板 */
  6.     for (int i = T.size() - 1; i >= 0; i--) {
  7.         while (!s.empty() && T[s.top()] <= T[i]) {
  8.             s.pop();
  9.         }
  10.         // 得到索引间距
  11.         res[i] = s.empty() ? 0 : (s.top() - i); 
  12.         // 将索引入栈，而不是元素
  13.         s.push(i); 
  14.     }
  15.     return res;
  16. }

数组遍历方向

构建单调栈时候，数组遍历方向取决于每次入栈的元素需要排除左边比它小的元素还是右边。待排除的数在左边就是顺序入栈，右边就是倒序入栈。

再来看一道Bad Hair Day：

Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.
Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

=
= =
= - = Cows facing right —>
= = =
= - = = =

= = = = = =

单调栈 - 图2

Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow’s hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow’s hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!

Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

题意:给定n头牛的高度，设d(i)为第i头牛可以看到(向右看)的其它牛的总数。

思路:反过来想，求第i头牛可以被左边多少头牛看到。维护一个单调栈即可。

这里需要保留每头牛被左边多少头牛看到的信息，所以这次需要从前往后遍历。即每头牛入栈前往左看，去除小于等于它的元素。等于是因为只有比它高的牛才能看到它，所以高度一样的牛依然需要排除在外

  1. #include<iostream>
  2. #include<vector>
  3. #include<stack>
  4. #include<utility>
  5. using namespace std;
  6. int main(int argc, char** argv){
  7.     int N;
  8.     cin>>N;
  9.     long total = 0;
  10.     int j = 0;
  11.     vector<int> h(N);
  12.     while(cin>>h[j]) j++;
  13.     stack<int> s;
  14.     for(int i = 0;i<N;i++){
  15.         while(!s.empty()&&s.top()<=h[i]){
  16.             s.pop();
  17.         }
  18.         total+=s.size();
  19.         s.push(h[i]);
  20.     }
  21.     printf("%lld",total);
  22.     return 0;
  23. }

单调栈讲解完毕，下面开始另一个重点：如何处理「循环数组」。

如何处理环形数组

同样是 Next Greater Number，现在假设给你的数组是个环形的，如何处理？力扣第 503 题「下一个更大元素 II」就是这个问题：

比如输入一个数组[2,1,2,4,3]，你返回数组[4,2,4,-1,4]。拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4。

一般是通过 % 运算符求模（余数），来获得环形特效：

  1. int[] arr = {1,2,3,4,5};
  2. int n = arr.length, index = 0;
  3. while (true) {
  4.     print(arr[index % n]);
  5.     index++;
  6. }

这个问题肯定还是要用单调栈的解题模板，但难点在于，比如输入是[2,1,2,4,3]，对于最后一个元素 3，如何找到元素 4 作为 Next Greater Number。

对于这种需求，常用套路就是将数组长度翻倍：

单调栈 - 图3

这样，元素 3 就可以找到元素 4 作为 Next Greater Number 了，而且其他的元素都可以被正确地计算。

有了思路，最简单的实现方式当然可以把这个双倍长度的数组构造出来，然后套用算法模板。但是，我们可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。

直接看代码吧：

  1. vector<int> nextGreaterElements(vector<int>& nums) {
  2.     int n = nums.size();
  3.     vector<int> res(n);
  4.     stack<int> s;
  5.     // 假装这个数组长度翻倍了
  6.     for (int i = 2 * n - 1; i >= 0; i--) {
  7.         // 索引要求模，其他的和模板一样
  8.         while (!s.empty() && s.top() <= nums[i % n])
  9.             s.pop();
  10.         res[i % n] = s.empty() ? -1 : s.top();
  11.         s.push(nums[i % n]);
  12.     }
  13.     return res;
  14. }

注意，这里结果赋值为res[i % n]，就是会覆盖前一次循环数组结果，以取得最终第一个循环体的结果。这样，就可以巧妙解决环形数组的问题，时间复杂度O(N)。