剑指Offer(二十):包含min函数的栈

  • A+
所属分类:剑指Offer
摘要

定义栈的数据结构,请在类型中实现一个能够得到栈最小元素的min函数。

剑指Offer(二十):包含min函数的栈

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

定义的数据结构,请在类型中实现一个能够得到最小元素的min函数。

1、思路

使用两个stack,一个为数据栈,另一个为辅助栈。数据栈用于存储所有数据,辅助栈用于存储最小值。

举个例子:

入栈的时候:首先往空的数据栈里压入数字3,显然现在3是最小值,我们也把最小值压入辅助栈。接下来往数据栈里压入数字4。由于4大于之前的最小值,因此我们只要入数据栈,不压入辅助栈。

出栈的时候:当数据栈和辅助栈的栈顶元素相同的时候,辅助栈的栈顶元素出栈。否则,数据栈的栈顶元素出栈。

获得栈顶元素的时候:直接返回数据栈的栈顶元素。

栈最小元素:直接返回辅助栈的栈顶元素。

2、代码

C++:

Python:

Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:12   其中:访客  7   博主  5

    • avatar 吖吖飒飒 来自天朝的朋友 Safari浏览器 iPad OS 10_3_3 like Mac OS X) AppleWebKit 上海市 联通 0

      弹出的时候,若相等则只有辅助站出吗?如3 4 2,按照上面逻辑 感觉会出来两个2

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学四舍(女生)

          @吖吖飒飒 为何是两个2?只要一个最小元素就可以了啊。

        • avatar Jac 来自天朝的朋友 谷歌浏览器 Mac OS X 10_13_3 广东省深圳市 电信 0

          交流下,假设先push 3,4,2, 此时Data栈顶是2;然后执行 pop() 后,此时Data栈顶还是2; 再执行top时得到是 2;这里是不是有问题?是不是需要去掉 else
          void pop() {
          if(Data.top() == Min.top()){
          Min.pop();
          }
          Data.pop();
          }

            • avatar Jack Cui Admin 来自天朝的朋友 火狐浏览器 Windows 7 北京市 百度网讯科技联通节点

              @Jac 没有吧,这程序是ac的。

            • avatar 寄生 来自天朝的朋友 QQ浏览器 Windows 10 陕西省西安市 电信 2

              同二楼疑问。
              void pop() {
              if(Data.top() == Min.top()){
              Min.pop();
              }
              else{
              Data.pop();
              }
              }
              这里,应该去掉else。两个栈顶元素相等,如果min栈出,而data栈不出,此时data栈存放最小值已经变了,而data栈没有变,这是不合理的。ac我也试了下过了,可能是测试用例有问题吧,但是逻辑应该照那样的。

                • avatar 寄生 来自天朝的朋友 QQ浏览器 Windows 10 陕西省西安市 电信 2

                  @寄生 有个地方打错了,此时data(应该为min)栈存放最小值已经变了

                    • avatar Jack Cui Admin 来自天朝的朋友 火狐浏览器 Windows 7 北京市 百度网讯科技联通节点

                      @寄生 恩恩,是的,有道理,已更正。

                        • avatar 寄生 来自天朝的朋友 谷歌浏览器 Windows 10 陕西省西安市 电信 2

                          @Jack Cui 博主,这是你的自建网站吗

                            • avatar Jack Cui Admin 来自天朝的朋友 火狐浏览器 Windows 7 北京市 百度网讯科技联通节点

                              @寄生 是的。

                      • avatar 爱看的剧 来自天朝的朋友 谷歌浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4

                        好像有问题啊。如果依次
                        push 2,2
                        pop()
                        此时按照这个程序的意思Min里面已经empty了啊,min函数就没用了啊,但data里面明明是有2的

                        • avatar 爱看的剧 来自天朝的朋友 谷歌浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4

                          line8改成 if(Min.top() >= value) ??

                            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市朝阳区 联通

                              @爱看的剧 没有问题啊,都ac了。等于的不用压入的,最小值就是2啊