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

  • 4
  • 104 °C
  • A+
所属分类:剑指Offer
摘要

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

举个例子:

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

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

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

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

2、代码

C++:

Jack Cui

发表评论

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

目前评论:4   其中:访客  2   博主  2

    • 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的。