单调栈

单调栈实际上是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后栈内的元素都保持有序（单调递增或递减）。它用于处理一种典型问题：Next Greater Element。

单调栈模板

给一个数组 nums，返回一个等长的结果数组，该数组中对应索引存储着下一个更大的元素，如果没有就存 -1。比如数组 nums = [2, 1, 2, 4, 3]，返回数组 [4, 2, 4, -1, -1]。

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

暴力解法很简单，就是对每个元素后面都进行扫描，找到第一个更大的元素即可，但时间复杂度为 O(N^2)。

问题可以抽象思考：将数组的元素想象成并列站立的人，元素大小想象成人的身高。如果能够看到元素⌈2⌋，那么后面可见的第一个人就是⌈2⌋的 Next Greater Number，因为比⌈2⌋小的元素身高都会被⌈2⌋挡住了，第一个露出的就是答案。

1.2.3 单调栈结构解决三道算法题 - 图1

  1. vector<int> nextGreateElement(vector<int>& nums) {
  2.     vector<int> res(nums.size());
  3.     stack<int> st;
  4.     for (int i = nums.size() - 1; i >= 0; --i) {
  5.         while (!s.empty() && s.top() <= nums[i])
  6.             s.pop();
  7.         res[i] = s.empty() ? -1 : s.top();
  8.         s.push(nums[i]);
  9.     }
  10.     return res;
  11. }

问题变形-每日温度

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

  1. 示例 1:
  3. 输入: temperatures = [73,74,75,71,69,72,76,73]
  4. 输出: [1,1,4,2,1,1,0,0]
  5. 示例 2:
  7. 输入: temperatures = [30,40,50,60]
  8. 输出: [1,1,1,0]
  9. 示例 3:
  11. 输入: temperatures = [30,60,90]
  12. 输出: [1,1,0]
  15. 提示：
  17. 1 <= temperatures.length <= 105
  18. 30 <= temperatures[i] <= 100
  20. 来源：力扣（LeetCode）
  21. 链接：https://leetcode-cn.com/problems/daily-temperatures
  22. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

和上题类似，本质上是找 Next Greater Number，只不过现在是求它的距离。

  1. vector<int> dailyTemperatures(vector<int>& temperatures) {
  2.     vector<int> res(temperatures.size());
  3.     stack<int> st;
  4.     for (int i = temperatures.size() - 1; i >= 0; --i) {
  5.         while (!st.empty() && temperatures[st.top()] <= temperatures[i])
  6.             st.top();
  7.         res[i] = st.empty() ? 0 : (st.top() - i);
  8.         st.push(i);
  9.     }
  10.     return res;
  11. }

问题变形II-循环数组（下一个更大元素II）

同样是求 Next Greater Number，现在的数组是环形的。

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-element-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

比如输入一个数组 [2, 1, 2, 4, 3]，返回数组 [4, 2, 4, -1, 4]。解释如上。一般可以通过 % 运算符求模（余数），来获得环形：

vector<int> arr = {1, 2, 3, 4, 5};
int len = arr.size(), index = 0;
while (true) {
    printf("arr[index % len] = %d\n", arr[index % len]);
    index++;
}

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

1.2.3 单调栈结构解决三道算法题 - 图2

这样元素 3 就可以找到元素 4 作为 Next Greater Number 了，其他元素都可以被正确计算出来。可以将双倍长度的数组构造出来，然后套用算法。但是，可以不构造新数组，利用循环数组的技巧来模拟数组长度翻倍的效果。

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    stack<int> st;
    for (int i = 2 * n - 1; i >= 0; --i) {
        // 索引需要求模
        while (!st.empty() && st.top() <= nums[i % n])
            s.pop();
        res[i % n] = st.empty() ? -1 : st.top();
        s.push(nums[i % n]);
    }

}