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

2017年12月9日15:59:54 24 3,759 °C
摘要

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

举个例子:

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

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

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

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

2、代码

C++:

Python:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

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

目前评论:24   其中:访客  14   博主  10

    • 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啊

                                • avatar lx 这家伙可能用了美佬的代理 谷歌浏览器 Mac OS X 10_14_1 美国 纽约 0

                                  @Jack Cui 同问,如果依次push7,push6,push3,push4,push3,pop3之后,得到的最小值应该还是3,但是按照你给的答案会返回6.

                                    • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 辽宁省沈阳市 联通GSM/WCDMA/LTE共用出口

                                      @lx 不会吧,连续push到data里,辅助栈一直是3,找到最小值,返回辅助栈栈顶元素,就是3。

                                        • avatar 你好帅呀 来自天朝的朋友 谷歌浏览器 Windows 7 安徽省合肥市 合肥工业大学 0

                                          @Jack Cui 辅助栈栈顶的3被pop掉了啊, 这时的栈顶应该是6

                                          • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                                            @你好帅呀 他说的是最后的3

                                    • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

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

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

                                          @小小毛 因为辅助栈存的是,当前最小的数。

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

                                          您好,在 push() 函数中,辅助栈只插入最小值,保证min()函数输出没有问题的前提是输入数据不包含重复数字,否则min()函数在遇到数据栈顶的与最小数相同的数(可能数据栈之前还有一个),则Min栈会弹出最小值,与题意不一致。所以建议修改push()函数和pop()函数。

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

                                              @walker class Solution:
                                              def __init__(self):
                                              self.Data = []
                                              self.Min = []
                                              def push(self, node):
                                              # write code here
                                              self.Data.append(node)
                                              if self.Min:
                                              if self.Min[-1] > node:
                                              self.Min.append(node)
                                              else:
                                              self.Min.append(self.Min[-1]) #保证Min栈的栈顶一直指向最小的数字,即使出现重复输入也不会出错
                                              else:
                                              self.Min.append(node)
                                              def pop(self):
                                              # write code here
                                              if self.Data == []:
                                              return None
                                              self.Min.pop()
                                              return self.Data.pop()
                                              def top(self):
                                              # write code here
                                              if self.Data == []:
                                              return None
                                              return self.Data[-1]
                                              def min(self):
                                              # write code here
                                              if self.Min == []:
                                              return None
                                              return self.Min[-1]

                                                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                                  @walker :wink: :wink: :wink:

                                              • avatar Scott 这家伙可能用了美佬的代理 谷歌浏览器 Mac OS X 10_14_6 美国 1

                                                您好,好像这个code无法解决pop最小值之后,再取min的情况?比如依次push {3,2,4,1}, 然后pop三次,再取min,此时Minstack 为空吧。
                                                可以考虑value大于Min.top()的时候,压入Min.top()自己

                                                  • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                                    @Scott 嗯,这个题,就是只要min,只要一个的情况。

                                                      • avatar Scott 这家伙可能用了美佬的代理 谷歌浏览器 Mac OS X 10_14_6 美国 伊利诺伊州尚佩恩县厄巴纳市伊利诺伊大学 1

                                                        @Jack Cui 嗯嗯,谢谢啦!