栈_栈top-程序员宅基地

技术标签: 算法    Algo  数据结构  

​ 栈是一种“先进后出”的线性数据结构。栈只有一端能够进出元素。能进出元素的一端叫栈顶,不能进出元素的一端叫栈底。当我们添加或者删除元素的时候,只能从栈顶操作。

image-20201205151854875

上图就是一个栈,栈里面有三个元素。其中 3 号元素是栈顶,1 号元素栈底。只有当前元素是栈顶的时候才能出栈。所以上图只有 3 号元素可以出栈。如果 3 号元素出栈,那么栈顶就会变成 2 号元素。

我们也可以用数组来模拟栈:

  • 定义数组和栈顶元素的位置,1 为栈底 : int stack[SIZE], top = 0;
  • 入栈 x : stack[++top] = x
  • 访问栈顶元素: stack[top]
  • 出栈: top--

一开始栈里面没有元素,所以 top 的值是 0top 可以代表栈顶所在的位置,也可以代表栈里面有多少个元素。

访问栈顶元素的时候,需要提前判断一下栈里面有没有元素,如果有才能返回栈顶元素。

例题

​ 实现一个栈,支持 Push(入栈)、Pop(出栈)和 GetMax (查询栈内元素的最大值)三个操作,要求时间复杂度均为 O(1).

思路:

​ 要求时间复杂度为O(1), 所以每 Push 一个元素的时候就要立刻知道最大值,所以我们可以定义一个变量 y 来表示当前栈里面元素的最大值,如果有元素进来,就可以和 y 比较一下,取最大就可以了。

image-20201205154625263

​ 具体来说,就是维护两个栈,栈 A 存储原本的数据,栈 B 存储栈 A 中以栈底开头的每段数据的最大值。如上图所示:

​ 当执行 Push(y) 的时候,在 A 中插入 y,在 B 中插入 max(y, B的栈顶数据)。在执行Pop操作时,在 A、B 两个栈中分别出栈。在执行 GetMax 操作时,取出 B栈的栈顶元素就可以了。

class Stack {
    
public:
    Stack() {
    
    	top = 0;  // 一开始栈为空, 所以 top = 0.
    }
    void Push(int value) {
      
    	A[++top] = value; // 首先把元素放到 A 栈里面。
    	B[top] = value;   // 直接放到 B 栈里面。 
    	if (top - 1 > 0) B[top] = max(B[top], B[top - 1]); // 如果之前 B 栈有元素, 那么比较一下,取个最大值。
    }
    
    void Pop() {
    
    	if (top > 0) --top;  // 元素个数减一。
    }
    int GetMax(){
    
    	return B[top]; // 取出最大的值,去之前需要判断一下栈里面有没有元素,这里我没有写。
    }
    int A[SIZE];  // A 栈
    int B[SIZE];  // B 栈
    int top;      // 栈顶元素的位置, 即栈内元素的个数。 
};

单调栈

单调栈内的元素是递增或者递减的。

单调栈的作用:

  • 求左面第一个大于或者小于当前元素的位置
  • 求右面第一个大于或者小于当前元素的位置
例题:

​ 一个数组 arr, 有 n 个数字, 对于每个位置的数字,求左边第一个小于当前数字的位置。

示例:

输入: arr = [2, 4, 6, 5, 3, 1, 8]
输出: [-1, 0, 1, 1, 0, -1, 5]

如果是暴力, 那就对每一个位置 i, 然后向前找,遇到大于等于当前数的接着找,直到找到一个小于的位置 j。

int n = arr.size(); // 数组大小
for (int i = 0; i < n; ++i){
      // 枚举每一个值
    int pos = -1; // 初始化位置, 如果找不到就是 -1
    for (int j = i-1; j >= 0; --j){
      // 枚举小于 i 的所有位置,一旦出现小于当前值的位置,就记录下来然后退出。
        if (arr[j] < arr[i]) {
    
            pos = j;
            break;
        }
    }
    ans.push_back(pos); // 记录答案
}

这样的时间复杂度是 O ( n 2 ) O(n^2) O(n2) 的。一点都不优雅,下面我们来了解一下更优雅的单调栈做法:

​ 对于 ii-1 这两个位置。i 可以复用 i-1 的情况。如果 arr[i] > arr[i-1], 那么 i 这个位置的答案就是 i-1, 否则 i 就要向前找,这个时候 i 就可以复用 i-1 的情况了, 因为 i-1 跳过的值就是 >= arr[i-1] 的, arr[i-1] >= a[i],所以 跳过的值必然也是 >= arr[i] 的, 所以这些值也就可以直接跳过。

​ 知道了上面的流程,就可以来了解怎么使用单调栈了。

​ 栈里面维护的是每个值的位置。当加入一个新值的时候,用新值不断的和栈顶代表的元素进行比较,如果新值大于栈顶,那么栈顶就是我们要找的位置, 否则就是新值小于等于栈顶所代表的数字,那么栈顶就要出栈。新值接着和栈顶进行下一次的比较。直到新值大于栈顶或者栈里面没有数字了。

​ 上面的步骤结束之后,记录答案,然后让新值的位置进栈,

总结一下就是: 每个值进栈的时候,都会弹掉前面那些大于等于自己的数字。

由于每个值最多进栈一次,出栈一次,所以时间复杂度是 O ( n ) O(n) O(n)

下面就是具体的代码:

stack<int>stk;
int sz = arr.size();
for (int i = 0; i < sz; ++i){
    
   while(stk.size() && arr[i] <= arr[stk.top()]) stk.pop(); // 如果当前的值 小于等于栈顶所代表的值, 就不断的弹栈,直到遇见大于当前的值
   L[i] = stk.size() ? stk.top() : -1;   // L 记录的是答案, 如果栈里面有值,记录的是栈顶的值,否之是 -1. 
   stk.push(i);  // 把当前位置压栈。
}

总的来说,单调栈是很好写的,我们也不需要知道这个栈是单调递增的还是单调递减的,只需要关心我们的目的就好了。是要求左边第一大于当前元素的位置还是左边第一个小于当前元素的位置。明确目的就可以直接写了。

训练题目:

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Top_xiao/article/details/110877329

智能推荐

联想WIN10解决intel vt-x问题_inter vtx-程序员宅基地

文章浏览阅读2.6w次,点赞11次,收藏29次。联想WIN10默认设置了【快速启动】,导致笔记本无法F12按进BIOS开启intelvt-x。解决办法:按住shift ,同时windows选择重启出现界面选择:疑难解答高级选项UEFI 固件设置重启,自动进入BISO界面Configuration-----Intel VirtualTechnology Disabled 改为 EnabledExit 保存修改退出..._inter vtx

NUTCH2.3 hadoop2.7.1 hbase1.0.1.1 solr5.2.1部署(三)_hbase_client_prefetch_limit-程序员宅基地

文章浏览阅读3.6k次。Precondition:hadoop 2.7.1hbase 0.98.13solr 5.2.1 / Apache Solr 4.8.1http://archive.apache.org/dist/lucene/solr/4.8.1/gora 0.6.1gora编译和Nutch编译部署1. Gora下载最新版本呢gora是0.6.1,下载或者直接通过_hbase_client_prefetch_limit

深度 | 刘群:基于深度学习的自然语言处理,边界在哪里?-程序员宅基地

文章浏览阅读361次。来源:AI科技评论编辑 | Camel四大边界:数据边界、语义边界、符号边界和因果边界当前,深度学习之于自然语言处理,有其局限性。那么它所能起作用的边界在哪里呢?对此..._基于word自然语言处理 基于character自然语言处理

linux下ad数模转换驱动程序设计,iTOP-4412开发板实现3路ADC数模转换驱动例程-程序员宅基地

文章浏览阅读290次。学习下 linux 数模程序驱动的编写,本节我们实现的功能是实现三路ADC 数模转换。驱动程序驱动程序的名字:“itop4412_adc.c”。要想把这个驱动注册到内核,先把这个驱动程序放到内核的“driver/char”目录下面,如下图所示: Makefile然后打开 drive/char 目录下面的 Makefile,添加:obj-$(CONFIG_ADC_CTL) += itop4412_a..._linux adc转换程序流程图

JS 获取滚动条位置_获取未滚动前y-程序员宅基地

文章浏览阅读1.3w次。执行代码,滚动鼠标滚轮:_获取未滚动前y

cocos2dx3.4开发环境搭建详解(2)_cocos_console_root 设置-程序员宅基地

文章浏览阅读4.3k次。本文主要介绍新建cocos2dx lua项目,运行新建的cocos2dx lua项目,并且解决一些新建和运行项目过程中可能会遇到的问题。版本仍然是cocos2dx3.4,本机配置仍然是64位的win7系统。_cocos_console_root 设置

随便推点

Java并发学习之停止基于线程的服务_producerexec.awaittermination-程序员宅基地

文章浏览阅读171次。一.停止基于线程的服务1.一般的应用程序中会创建多个线程的服务,例如线程池,我们创建一个线程池的服务时,它会又创建多个线程,如果我们不关闭服务,它会一直存在,所以服务的生命周期通常比创建它们的方法的生命周期更长。如果应用程序准备退出,应用程序会关闭服务,服务又会关闭它拥有的线程。由于无法通过抢占式的方法来停止线程,所以它们需要自行关闭。2.我们对线程的封装原则是:除非拥有某个线程,否则不能对该线程进行操控。线程有一个相应的所有者(创建它的类),因此线程池是其他工作者线程的所有者,如果要中断这些线程,那么_producerexec.awaittermination

使用 Microsoft.UI.Xaml 解决 UWP 控件和对老版本 Windows 10 的兼容性问题-程序员宅基地

文章浏览阅读1.7k次。使用 Microsoft.UI.Xaml 解决 UWP 控件和对老版本 Windows 10 的兼容性问题 原文 使用 Microsoft.UI.Xaml 解决 UWP 控件和对老版本 Windows 10 的兼容性问题虽然微软宣称 Windows 10 将是最后一个 Windows 版本,但由于年代跨越实在太久远,兼容性依然是避不开的问题..._wpf程序使用microsoft.ui.xaml

dedecms教程:20位MD5加密密文解密示例介绍_20位加密串 怎么计算-程序员宅基地

文章浏览阅读896次。解密20位md5,20位md5加密算法。 dedecms的20位md5加密算噶是从32位md5中截取的20位,所以去掉前3位喝最后1位,即可获得16位md5值,即可破解15位md5。 例如:数据库的密文是f297a57a5a743894a0e4 得到20位MD5密码,前减3后,再去掉最后1位,得到16位MD5,这样就获得7a57a5a743894a0e 如果密文不能_20位加密串 怎么计算

用ifconfig命令,显示结果只有lo,没有eth0_银河麒麟ifconfig只有lo和sit0-程序员宅基地

文章浏览阅读9k次。解决1. 输入ifconfig -a命令,可以看到eth0和lo。2. 进入/etc/sysconfig/network-scripts 目录,发现有ifcfg-eth0,即网卡(驱动)存在但未启用。3. 输入ifconfig eth0 up,启用网卡。此时用ifconfig,只能看到inet6的地址,没有ip4. vi /etc/sysconfig/network-scrip_银河麒麟ifconfig只有lo和sit0

微信多开软件工具及批处理文件教程_微信多开批处理文件-程序员宅基地

文章浏览阅读487次,点赞13次,收藏9次。微信多开小工具,通过批处理文件用于实现微信多开的功能。_微信多开批处理文件

vulnhub DC7 靶场练习_dc7靶场-程序员宅基地

文章浏览阅读1.6k次,点赞2次,收藏2次。前言这次练习的靶机是vulnhub平台下的DC系列靶机第7台,下载地址为https://www.vulnhub.com/entry/dc-7,356/。挑战该靶机的最终目的是获取root权限,然后读取唯一的flag。这台靶机中用暴力破解成功的概率非常小,我们需要开阔思路,寻找非技术上的方法。虚拟机配置这次采用的网络连接模式依然是NAT模式,为了避免扫描到其他物理主机。在导入虚拟机后,右击DC-6靶机,然后选中配置。依次点击网络配置->NAT模式->高级->生成,然后确认即可。收集_dc7靶场

推荐文章

热门文章

相关标签