原始单调栈模板

当要寻找最近的下一个更大元素时，就需要使用单调栈（栈中元素单调递减）。

单调栈代码模板：

如下代码中单调栈直接存的元素值，有些题目的情形下单调栈需要存储元素下标，视情况而定

  1. class Solution {
  2. public:
  3.     // 寻找数组 nums 中每个元素的下一个更大元素，存储到 answer 数组
  4.     vector<int> nextGreaterElements(vector<int>& nums) {
  5.         vector<int> answer(nums.size(), 0);        // 存放答案的数组
  6.         stack<int> s;                            // 单调栈                                        // 单调栈，存储下标而非元素
  7.           // 倒着遍历数组，存入单调栈
  8.         for(int i = nums.size() - 1; i >= 0; --i)
  9.         {
  10.               // 如果单调栈不为空，且栈顶存的元素小于等于当前元素，
  11.               // 那么其存在没有意义，直接pop掉
  12.               // 因为栈顶元素前面有更大元素存在（即当前元素），对于更往前的元素，这个top不可能作为其最近更大元素
  13.             while(!s.empty() && s.top() <= nums[i])
  14.                 s.pop();
  15.               // 获得当前元素的下一个更大元素 answer[i]：
  16.               // - 如果单调栈为空，说明往后不存在更大的元素，答案记为 -1
  17.               // - 如果单调栈不为空，则当前栈顶就是下一个更大元素
  18.             answer[i] = s.empty() ? -1 : s.top();
  19.               // 将当前元素入栈
  20.             s.push(nums[i]);
  21.         }
  22.         return answer;
  23.     }
  24. };

复杂度分析：数组长度 n

  • 时间复杂度 O(n)：数组中的每个元素，都会进栈一次，最多出栈一次
  • 空间复杂度 O(n)：单调栈最坏情况下存储 n 个元素， 即数组单调递增的情况（那么逆序遍历数组时，遍历到的元素单调递减，因此会不断存入单调栈，而不会弹出）

题目1：单调栈存元素

[简单] 496. 下一个更大元素 I

题目2：单调栈存下标

[中等] 739. 每日温度

环形数组 - 单调栈模板

如果给定的数组是环形数组，那么常用套路是将数组长度翻倍（复制一份拼接在后面）。

  • 当然实际上不用真的将数组 nums 复制一份，具体看下面代码
  • 和原始的单调栈模板就两点不同，具体如下面代码所示
    1. 改动一：假装 nums 数组长度翻倍了，从翻倍后的位置开始逆序遍历
    2. 改动二：索引都要改为求模（i % len，len 是数组长度）
      class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
  int len = nums.size();            // 数组长度
  vector<int> answer(len, -1);    // 存放答案的数组
  stack<int> s;                    // 单调栈
    // 改动一：假装 nums 数组长度翻倍了，从翻倍后的位置开始逆序遍历
  for(int i = len * 2 - 1; i >= 0; --i)
  {
        // 改动二：如下的索引都要求模，其它和原始的单调栈模板一致
      while(!s.empty() && s.top() <= nums[i % len])
          s.pop();
      answer[i % len] = s.empty() ? -1 : s.top();
      s.push(nums[i % len]);
  }
  return answer;
}
};

题目1：环形数组（单调栈存元素）

[中等] 503. 下一个更大元素 II