单调栈

用法

 给你一个数组,要求你找到数组中每个元素左边第一个比他大的数和右边第一个比它大的数,举个例子,数组[3,5,2,1,6],3左边比他大的没有,右边比他大的是5;5左边比它大的没有,右边比他大的是6;2左边比它大的是5,右边比他大的是6;1左边比他大的是2,右边比他大的是6;6左边比他大的没有,右边比它大的没有

单调栈应用

 上面的问题,直接遍历可以,但是如果利用单调栈来做,可以保证时间复杂度为O(n)。首先说明一下什么是单调栈,单调栈就是栈内元素都是严格单调递增或单调递减的,根据题目具体情况。  看一下单调栈的工作过程(这里是单调递减栈,就是从栈底到栈顶是递减的),还是以nums = [3,5,2,1,6]为例,单调栈存的是数组下标。  首先,栈空,所以下标0直接入栈;  然后到了下标1,因为nums[stack.peek()] < nums[1],所以栈顶元素出栈,在出栈的时候记录是什么值让我出栈的,在这里是下标值1让栈顶出栈,所以栈顶元素的右边比他大的数的下标就是1,然后看当前值出栈前,在栈内排在我下面的值是谁,因为0下面没有值,所以是空,因此nums[0]的左边比他大的数没有,右边比它大的数是nums[1];  继续,因为nums[1] > nums[2],所以2直接进栈;  3也直接进栈,此时栈内从栈底到栈顶依次是1,2,3;  然后来到了4,因为nums[stack.peek()] < nums[4],所以stack.pop(),3出栈,出栈的时候开始记录,在栈内,3底下的数是2,所以3左边比他大的数的下标是2,因为4要进栈,导致3出栈,所以4是3右边比它大的数的下标;  因为nums[stack.peek()] < nums[4],所以还要继续出栈,此时出栈的值是2,按照之前的规则,2左边比他大的数的下标就是1,2右边比它大的数的下标就是4;  因为nums[stack.peek()] < nums[4],所以依然继续出栈,此时出栈的值是1,1左边比它大的数没有,右边比它大的数的下标是4;  现在栈是空的,所以4直接进栈了,然后到了数组的边界,因此栈内剩下的所有值都直接弹出,并且按照之前的规则,记录每一个值,因为没有元素要进栈,而是便利到了数组结尾导致他们要出栈,所以栈内所有的值右边比它大的数的下标都是空,左边比它大的数的下标就是在栈内,他们下面的数。对于当前栈内情况来看,4左边比它大的数的下标和右边比它大的数的下标都是空。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CIFAR-10数据集实战——构建LeNet5神经网络

    如果从官网下载数据集很慢,可以使用国内的地址http://ai-atest.bj.bcebos.com/cifar-10-python.tar.gz

    mathor
  • Siamese Network & Triplet NetWork

    在孪生网络中,我们把一张图片$X_1$作为输入,得到该图片的编码$G_W(X_1)$。然后,我们在不对网络参数进行任何更新的情况下,输入另一张图片$X_2$,并...

    mathor
  • 百度语音合成模型Deep Voice3

    Deep Voice3是由百度提出的一个全新的全卷积TTS架构。百度的主要工作分为如下五个方面:

    mathor
  • SD-WAN平台ActiveCore推出,领域新亮点精彩丰呈

    Comcast Business发布了一款名为ActiveCore的软件定义网络(SDN)平台,该公司宣布其软件定义广域网(SD-WAN)业务产品将成为第一款由...

    SDNLAB
  • 【每日算法Day 78】面试经典题:能说出全部四种方法,不录用你都不可能!

    用 $dpi$ 表示位置 $i$ 是否可达,初始的时候都是 $0$ ,只有 $dp0 = 1$ ,因为起点一定是可达的。

    godweiyang
  • 笔记80 | Eclipse环境下利用NDK编译SO文件

    下载地址 ,选择一个版本对应下载之后解压,注意路径不要有中文,请直接使用版本【android-ndk-r14b】,不要问为什么,都是泪;

    项勇
  • 2018中国SD-WAN峰会直击——工信部科技委信息通信网络专家组组长赵慧玲女士发表主题演讲:网络技术的发展和挑战

    今天2018 SD-WAN峰会在北京召开,工信部科技委信息通信网络专家组组长赵慧玲女士为我们带来主题演讲“网络技术的发展和挑战”。

    SDNLAB
  • 分布式跟踪工具Pinpoint初探

    由于工作需要,前段时间抽口研究了一下APM相关技术。 大的互联网公司都有自己的分布式跟踪系统,比如Google的Dapper,Twitter的zipkin,淘宝...

    小柒2012
  • BRAIN:中重度脑外伤后进行性脑体积萎缩的空间模式

    脑外伤导致显著脑体积萎缩并持续至慢性期,可被MRI容积分析测量。来自英国帝国理工学院计算,认知和临床神经成像实验室David J Sharp研究组对中重度脑外伤...

    用户1279583
  • 刘知远:近年来开源的算法代码、工具包列表

    数据派THU

扫码关注云+社区

领取腾讯云代金券