特殊数据结构:单调栈

引言

栈(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」挡住了,第一个露出来的就是答案。

特殊数据结构:单调栈插图

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

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

这就是单调队列解决问题的模板。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 的距离而已。

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

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

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

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

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

特殊数据结构:单调栈插图(1)

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

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

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

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

特殊数据结构:单调栈插图(2)

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

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n); // 存放结果
    stack<int> s;
    // 假装这个数组长度翻倍了
    for (int i = 2 * n - 1; i >= 0; i--) {
        while (!s.empty() && s.top() <= nums[i % n])
            s.pop();
        res[i % n] = s.empty() ? -1 : s.top();
        s.push(nums[i % n]);
    }
    return res;
}

初步来总结一下单调栈吧,单调栈其实是一个看似原理简单,但是可以变得很难的解法。线性的时间复杂度是其最大的优势,每个数字只进栈并处理一次,而解决问题的核心就在处理这块,当前数字如果破坏了单调性,就会触发处理栈顶元素的操作,而触发数字有时候是解决问题的一部分,比如在 Trapping Rain Water 中作为右边界。有时候仅仅触发作用,比如在 Largest Rectangle in Histogram 中是为了开始处理栈顶元素,如果仅作为触发,可能还需要在数组末尾增加了一个专门用于触发的数字。另外需要注意的是,虽然是递增或递减栈,但里面实际存的数字并不一定是递增或递减的,因为我们可以存坐标,而这些坐标带入数组中才会得到递增或递减的数。所以对于玩数组的题,如果相互之间关联很大,那么就可以考虑考虑单调栈能否解题。


另外,单调栈也可以用于离线解决 RMQ 问题

我们可以把所有询问按右端点排序,然后每次在序列上从左往右扫描到当前询问的右端点处,并把扫描到的元素插入到单调栈中。这样,每次回答询问时,单调栈中存储的值都是位置 (le r) 的、可能成为答案的决策点,并且这些元素满足单调性质。此时,单调栈上第一个位置 (ge l) 的元素就是当前询问的答案,这个过程可以用二分查找实现。使用单调栈解决 RMQ 问题的时间复杂度为 (O(qlog q + qlog n)) ,空间复杂度为 (O(n))

参考资料

CSDN:单调栈介绍

博客园:单调栈小结

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 特殊数据结构:单调栈

发表评论

免登录下载网,提供全网最优质的资源集合!