如何使用单调栈解题

栈(stack)是很简单的一种数据结构,先进后出的逻辑顺序,符合某些问题的特点,比如说函数调用栈。

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

听起来有点像堆(heap)?不是的,单调栈用途不太广泛,只处理一种典型的问题,叫做 Next Greater Element。本文用讲解单调队列的算法模版解决这类问题,并且探讨处理「循环数组」的策略。

首先,讲解 Next Greater Number 的原始问题:给你一个数组,返回一个等长的数组,对应索引存储着下一个更大元素,如果没有更大的元素,就存 -1。不好用语言解释清楚,直接上一个例子:

给你一个数组 [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」挡住了,第一个露出来的就是答案。

ink-image

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

  1. vector<int> nextGreaterElement(vector<int>& nums) {
  2. vector<int> ans(nums.size()); // 存放答案的数组
  3. stack<int> s;
  4. for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放
  5. while (!s.empty() && s.top() <= nums[i]) { // 判定个子高矮
  6. s.pop(); // 矮个起开,反正也被挡着了。。。
  7. }
  8. ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个
  9. s.push(nums[i]); // 进队,接受之后的身高判定吧!
  10. }
  11. return ans;
  12. }

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

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

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

现在,你已经掌握了单调栈的使用技巧,来一个简单的变形来加深一下理解。

给你一个数组 T = [73, 74, 75, 71, 69, 72, 76, 73],这个数组存放的是近几天的天气气温(这气温是铁板烧?不是的,这里用的华氏度)。你返回一个数组,计算:对于每一天,你还要至少等多少天才能等到一个更暖和的气温;如果等不到那一天,填 0 。

举例:给你 T = [73, 74, 75, 71, 69, 72, 76, 73],你返回 [1, 1, 4, 2, 1, 1, 0, 0]。

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

你已经对 Next Greater Number 类型问题有些敏感了,这个问题本质上也是找 Next Greater Number,只不过现在不是问你 Next Greater Number 是多少,而是问你当前距离 Next Greater Number 的距离而已。

相同类型的问题,相同的思路,直接调用单调栈的算法模板,稍作改动就可以啦,直接上代码把。

  1. vector<int> dailyTemperatures(vector<int>& T) {
  2. vector<int> ans(T.size());
  3. stack<int> s; // 这里放元素索引,而不是元素
  4. for (int i = T.size() - 1; i >= 0; i--) {
  5. while (!s.empty() && T[s.top()] <= T[i]) {
  6. s.pop();
  7. }
  8. ans[i] = s.empty() ? 0 : (s.top() - i); // 得到索引间距
  9. s.push(i); // 加入索引,而不是元素
  10. }
  11. return ans;
  12. }

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

同样是 Next Greater Number,现在假设给你的数组是个环形的,如何处理?

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

ink-image

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

  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. }

回到 Next Greater Number 的问题,增加了环形属性后,问题的难点在于:这个 Next 的意义不仅仅是当前元素的右边了,有可能出现在当前元素的左边(如上例)。

明确问题,问题就已经解决了一半了。我们可以考虑这样的思路:将原始数组“翻倍”,就是在后面再接一个原始数组,这样的话,按照之前“比身高”的流程,每个元素不仅可以比较自己右边的元素,而且也可以和左边的元素比较了。

ink-image (2)

怎么实现呢?你当然可以把这个双倍长度的数组构造出来,然后套用算法模板。但是,我们可以不用构造新数组,而是利用循环数组的技巧来模拟。直接看代码吧:

  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. while (!s.empty() && s.top() <= nums[i % n])
  8. s.pop();
  9. res[i % n] = s.empty() ? -1 : s.top();
  10. s.push(nums[i % n]);
  11. }
  12. return res;
  13. }

至此,你已经掌握了单调栈的设计方法及代码模板,学会了解决 Next Greater Number,并能够处理循环数组了。