剑指Offer（二十）：包含min函数的栈

2017年12月9日15:59:54 24 3,805 °C

摘要

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

一、前言

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

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

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

举个例子：

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

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

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

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

2、代码

C++：

class Solution {
public:
    void push(int value) {
        Data.push(value);
        if(Min.empty()){
            Min.push(value);
        }
        if(Min.top() > value){
            Min.push(value);
        }
    }
    void pop() {
        if(Data.top() == Min.top()){
            Min.pop();
        }
        Data.pop();
    }
    int top() {
        return Data.top();
    }
    int min() {
        return Min.top();
    }
private:
    stack<int> Data;			//数据栈
    stack<int> Min;				//最小栈
};

class Solution {

public:

void push(int value) {

Data.push(value);

if(Min.empty()){

Min.push(value);

}

if(Min.top() > value){

Min.push(value);

}

void pop() {

if(Data.top() == Min.top()){

Min.pop();

}

Data.pop();

}

int top() {

return Data.top();

}

int min() {

return Min.top();

}

private:

stack<int> Data; //数据栈

stack<int> Min; //最小栈

};

Python：

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]

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]

微信公众号

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

版权声明：本站原创文章，于2017年12月9日15:59:54，由 Jack Cui 发表，共 395 字。
转载请注明：剑指Offer（二十）：包含min函数的栈 | Jack Cui

发表评论取消回复

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

吖吖飒飒 上海市联通 0
回复 2018年4月25日上午12:19 沙发
弹出的时候，若相等则只有辅助站出吗？如3 4 2，按照上面逻辑感觉会出来两个2
- Jack Cui Admin 辽宁省沈阳市东北大学四舍(女生)
  回复 2018年4月25日上午8:12 1层
  @吖吖飒飒为何是两个2？只要一个最小元素就可以了啊。
Jac 广东省深圳市电信 0
回复 2018年5月20日下午3:29 板凳
交流下，假设先push 3，4，2，此时Data栈顶是2；然后执行 pop() 后，此时Data栈顶还是2；再执行top时得到是 2；这里是不是有问题？是不是需要去掉 else
void pop() {
if(Data.top() == Min.top()){
Min.pop();
}
Data.pop();
}
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2018年5月21日上午10:25 1层
  @Jac 没有吧，这程序是ac的。
寄生陕西省西安市电信 2
回复 2018年6月5日上午2:41 地板
同二楼疑问。
void pop() {
if(Data.top() == Min.top()){
Min.pop();
}
else{
Data.pop();
}
}
这里，应该去掉else。两个栈顶元素相等，如果min栈出，而data栈不出，此时data栈存放最小值已经变了，而data栈没有变，这是不合理的。ac我也试了下过了，可能是测试用例有问题吧，但是逻辑应该照那样的。
- 寄生陕西省西安市电信 2
  回复 2018年6月5日上午2:43 1层
  @寄生有个地方打错了，此时data（应该为min）栈存放最小值已经变了
  - Jack Cui Admin 北京市百度网讯科技联通节点
    回复 2018年6月5日上午9:39 2层
    @寄生恩恩，是的，有道理，已更正。
    - 寄生陕西省西安市电信 2
      回复 2018年6月7日下午7:34 3层
      @Jack Cui 博主，这是你的自建网站吗
      - Jack Cui Admin 北京市百度网讯科技联通节点
        2018年6月7日下午7:48 4层
        @寄生是的。
爱看的剧 上海市上海理工大学 4
回复 2018年7月20日下午9:04 4楼
好像有问题啊。如果依次
push 2，2
pop()
此时按照这个程序的意思Min里面已经empty了啊，min函数就没用了啊，但data里面明明是有2的
爱看的剧 上海市上海理工大学 4
回复 2018年7月20日下午9:13 5楼
line8改成 if(Min.top() >= value) ？？
- Jack Cui Admin 北京市朝阳区联通
  回复 2018年7月20日下午9:29 1层
  @爱看的剧没有问题啊，都ac了。等于的不用压入的，最小值就是2啊
  - lx 美国纽约 0
    回复 2018年12月9日上午4:54 2层
    @Jack Cui 同问，如果依次push7,push6,push3,push4,push3,pop3之后，得到的最小值应该还是3，但是按照你给的答案会返回6.
    - Jack Cui Admin 辽宁省沈阳市联通GSM/WCDMA/LTE共用出口
      回复 2018年12月9日上午9:35 3层
      @lx 不会吧，连续push到data里，辅助栈一直是3，找到最小值，返回辅助栈栈顶元素，就是3。
      - 你好帅呀 安徽省合肥市合肥工业大学 0
        2019年3月6日下午4:28 4层
        @Jack Cui 辅助栈栈顶的3被pop掉了啊，这时的栈顶应该是6
      - Jack Cui Admin 北京市百度网讯科技联通节点
        2019年3月8日上午9:59 4层
        @你好帅呀他说的是最后的3
小小毛 天津市天津大学 3
回复 2019年7月3日下午2:36 6楼
为什么“出栈的时候：当数据栈和辅助栈的栈顶元素相同的时候，辅助栈的栈顶元素出栈。否则，数据栈的栈顶元素出栈。”
- Jack Cui Admin 北京市大兴区联通
  回复 2019年7月3日下午10:04 1层
  @小小毛因为辅助栈存的是，当前最小的数。
walker 陕西省西安市电信 1
回复 2019年9月1日下午8:12 7楼
您好，在 push() 函数中，辅助栈只插入最小值，保证min()函数输出没有问题的前提是输入数据不包含重复数字，否则min()函数在遇到数据栈顶的与最小数相同的数（可能数据栈之前还有一个）,则Min栈会弹出最小值,与题意不一致。所以建议修改push()函数和pop(）函数。
- walker 陕西省西安市电信 1
  回复 2019年9月1日下午8:26 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]
  - Jack Cui Admin 北京市百度网讯科技联通节点
    回复 2019年9月2日上午9:27 2层
    @walker
Scott 美国 1
回复 2020年3月11日上午10:12 8楼
您好，好像这个code无法解决pop最小值之后，再取min的情况？比如依次push {3,2,4,1}, 然后pop三次，再取min，此时Minstack 为空吧。
可以考虑value大于Min.top()的时候，压入Min.top()自己
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2020年3月11日下午5:18 1层
  @Scott 嗯，这个题，就是只要min，只要一个的情况。
  - Scott 美国伊利诺伊州尚佩恩县厄巴纳市伊利诺伊大学 1
    回复 2020年3月11日下午8:50 2层
    @Jack Cui 嗯嗯，谢谢啦！

一、前言

二、题目

1、思路

2、代码

发表评论取消回复

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

登录 注册 找回密码

登录注册找回密码