0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

单调栈解题模板如何秒杀三道算法题

jf_78858299 来源:labuladong 作者:labuladong 2023-04-19 10:52 次阅读

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

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

单调栈模板

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

给你一个数组,返回一个等长的数组,对应索引存储着下一个更大元素,如果没有更大的元素,就存 -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」挡住了,第一个露出来的就是答案。

图片

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

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

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

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

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

问题变形

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

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

函数签名如下:

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 的距离而已。

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

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

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

如何处理环形数组

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

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

一般是通过 % 运算符求模(余数),来获得环形特效:

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

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

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

图片

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

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

直接看代码吧:

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

这样,就可以巧妙解决环形数组的问题,时间复杂度O(N)

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92856
  • 数组
    +关注

    关注

    1

    文章

    417

    浏览量

    25942
收藏 人收藏

    评论

    相关推荐

    什么是模板匹配?模板匹配的原理讲解 图像处理与模板匹配算法

    目标。模板就是我们已知的在图中要找的目标,且该目标同模板有相同的尺寸、方向和图像,通过一定的算法可以在图中找到目标,确定其坐标位置。 二:模板匹配的原理 用通俗的语言来解释
    的头像 发表于 05-05 09:25 3.4w次阅读
    什么是<b class='flag-5'>模板</b>匹配?<b class='flag-5'>模板</b>匹配的原理讲解 图像处理与<b class='flag-5'>模板</b>匹配<b class='flag-5'>算法</b>

    嵌入式开发经典算法逆序

    不借助其他数据结构,如何实现的逆序?这是一非常经典的算法笔试题。
    发表于 08-06 17:10 370次阅读

    单片机8031、四、五。一10元

    单片机8031、四、五。一10元,直接发我qq840921270 ,会给第一个采用
    发表于 04-16 17:02

    2018年全国大学生数学建模竞赛B题解题程序----广西大学 69队

    ......星期四晚上拿到赛,按照惯例应该是请假全身心投入比赛,呃呃...然而并没有请假...大致看了A、B两,A题目短...估计坑多...于是选了B。。B
    发表于 05-31 12:15

    自动控制原理解题

    自动控制原理解题典是根据高等工科院校自动控制原理教学大纲的基本要求编写的,书中例题涵盖了经典控制理论和线性系统状态空间分析的基本内容。全书共分九章,每章均
    发表于 07-11 09:01 93次下载
    自动控制原理<b class='flag-5'>解题</b><b class='flag-5'>题</b>典

    模板方法模式在回溯算法中的应用

    描述了模板方法模式及回溯算法模板方法模式的Java 语言实现,该实现使得回溯算法的实现达到了可扩展性、灵活性和可插入性个目标,提高了
    发表于 01-15 16:48 20次下载

    模板方法模式在回溯算法中的应用

    描述了模板方法模式及回溯算法模板方法模式的Java 语言实现,该实现使得回溯算法的实现达到了可扩展性、灵活性和可插入性个目标,提高了
    发表于 01-15 16:51 0次下载

    国内开发者在GitHub上开源LeetCode刷模板

    为了更好的与开发者分享自己的刷技巧,greyireland 在 GitHub 上开源了一套 LeetCode 刷模板:algorithm-pattern,主要记录他通过各种刷文章
    的头像 发表于 07-01 15:03 1819次阅读
    国内开发者在GitHub上开源LeetCode刷<b class='flag-5'>题</b><b class='flag-5'>模板</b>!

    快来,我出个算法给你做做

    考大家一个算法 责任编辑:xj 原文标题:考大家一个算法 文章出处:【微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。
    的头像 发表于 10-10 16:55 1401次阅读

    一篇文章秒杀区间相关的问题

    经常有读者问区间相关的问题,今天写一篇文章,秒杀区间相关的问题。 所谓区间问题,就是线段问题,让你合并所有线段、找出线段的交集等等。主要有两个技巧: 1、排序。常见的排序方法就是按照区间起点排序
    的头像 发表于 10-12 14:54 1892次阅读
    一篇文章<b class='flag-5'>秒杀</b><b class='flag-5'>三</b><b class='flag-5'>道</b>区间相关的问题

    深入浅出了解单调单调队列

    袁厨携袁记菜馆全体工作人员祝大家在新的一年,健健康康,开开心心。发量暴增,钱包超大。 哎,元旦假期结束了,又要继续搬砖了,我们接着做题吧,今天我们好好说说单调单调队列。其实很容易理解,单调
    的头像 发表于 02-02 10:18 1478次阅读
    深入浅出了解<b class='flag-5'>单调</b><b class='flag-5'>栈</b>和<b class='flag-5'>单调</b>队列

    如何用DFS算法秒杀岛屿系列问题

    DFS/BFS 算法遍历二维数组 。 本文主要来讲解如何用 DFS 算法秒杀岛屿系列问题,不过用 BFS 算法的核心思路是完全一样的,无非就是把 DFS 改写成 BFS 而已。 那
    的头像 发表于 11-16 17:13 1750次阅读
    如何用DFS<b class='flag-5'>算法</b>来<b class='flag-5'>秒杀</b>岛屿系列问题

    DFS算法秒杀岛屿系列问题

    本文主要来讲解如何用 DFS 算法秒杀岛屿系列问题,不过用 BFS 算法的核心思路是完全一样的,无非就是把 DFS 改写成 BFS 而已。
    的头像 发表于 04-19 10:39 567次阅读
    DFS<b class='flag-5'>算法</b><b class='flag-5'>秒杀</b>五<b class='flag-5'>道</b>岛屿系列问题

    数据结构解决滑动窗口问题

    前文用 [单调解决算法问题]介绍了单调这种特
    的头像 发表于 04-19 10:50 656次阅读
    数据结构解决滑动窗口问题

    滑动窗口算法解决子串问题教程

    难但太复杂,所以本文只选择点赞最高,较为经典的,最能够讲明白的来讲解。第一题为了让读者掌握算法模板,篇幅相对长,后两
    的头像 发表于 04-19 11:06 739次阅读
    滑动窗口<b class='flag-5'>算法</b>解决子串问题教程