首页 > 试题广场 >

包含min函数的栈

[编程题]包含min函数的栈
  • 热度指数：648165 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

数据范围：操作数量满足 ，输入的元素满足
进阶：栈的各个操作的时间复杂度是 ，空间复杂度是

示例:
输入:    ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出:    -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中，栈中元素为-1
"PSH2"表示将2压入栈中，栈中元素为2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素，弹出2，栈中元素为-1
"PSH1"表示将1压入栈中，栈中元素为1，-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1

示例1

输入

 ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

输出

-1,2,1,-1
算法知识视频讲解
查看答案及解析
添加回答
推荐
Ron头像 Ron 
import java.util.Stack;
import java.util.Arrays;
public class Solution {
/*借用辅助栈存储min的大小，自定义了栈结构
*/
    private int size;
    private int min = Integer.MAX_VALUE;
    private Stack<Integer> minStack = new Stack<Integer>();
    private Integer[] elements = new Integer[10];
    public void push(int node) {
        ensureCapacity(size+1);
        elements[size++] = node;
        if(node <= min){
            minStack.push(node);
            min = minStack.peek();
        }else{
            minStack.push(min);
        }
    //    System.out.println(min+"");
    }

    private void ensureCapacity(int size) {
        // TODO Auto-generated method stub
        int len = elements.length;
        if(size > len){
            int newLen = (len*3)/2+1; //每次扩容方式
            elements = Arrays.copyOf(elements, newLen);
        }
    }
    public void pop() {
        Integer top = top();
        if(top != null){
            elements[size-1] = (Integer) null;
        }
        size--;
        minStack.pop();    
        min = minStack.peek();
    //    System.out.println(min+"");
    }

    public int top() {
        if(!empty()){
            if(size-1>=0)
                return elements[size-1];
        }
        return (Integer) null;
    }
    public boolean empty(){
        return size == 0;
    }

    public int min() {
        return min;
    }
}

编辑于 2015-06-19 17:57:04 回复(57)
Python
HHHChen77头像 HHHChen77
1.利用辅助栈存当前栈最小值
   时间复杂度：O(1)
   空间复杂度：O(n) 
class Solution:
    def __init__(self):
        #定义两个栈,一个为原始栈,一个为辅助存min的栈
        #原栈
        self.stack = []
        #存储当前栈的最小值
        self.assist = []
    def push(self, node):
        # write code here
        # 栈为空,直接压栈
        if not self.stack:
            self.assist.append(node)
            self.stack.append(node)
        else:
            #当前栈的最小值
            min_now = self.min()
            #压栈前判断该值是不是最小值
            #若大于当前栈最小值，则辅助栈继续压入当前最小值
            if node > min_now:
                self.assist.append(min_now)
            else:
                self.assist.append(node)
            self.stack.append(node)
    def pop(self):
        # write code here
        # 同时弹栈
        self.assist.pop()
        return self.stack.pop()
    def top(self):
        # write code here
        #返回末尾数据，即原始栈顶
        return self.stack[-1]
    def min(self):
        # write code here
        #返回辅助栈栈顶，记录当前最小值
        return self.assist[-1]
2.使用变量记录栈当前最小值，压栈的对象为原始数据与当前最小值的差值
   时间复杂度：O(1)
   空间复杂度：O(1) 
class Solution:
    def __init__(self):
        # 压入栈的数字为 原始数字与当前栈最小值的差值
        self.stack = []
        # 动态记录当前栈的最小值
        self.min_num = 0
    def push(self, node):
        # write code here
        # 栈为空,当前第一个数为最小,差为0
        if not self.stack:
            self.stack.append(0)
            self.min_num = node
        else:
            # 与当前最小值求差
            compare = node - self.min_num
            self.stack.append(compare)
            # node小于最小值,更新node为当前最小值
            if compare < 0:
                self.min_num = node
    def pop(self):
        # write code here
        # 判断栈顶数据正负
        peek = self.stack.pop()
        if peek < 0:
            # 栈顶就是当前最小值
            now = self.min_num
            # 弹出后的最小值更新为上一个最小值
            self.min_num = self.min_num - peek
            return now
        else:
            # 栈顶不是当前最小值
            # 根据当前最小值和差值计算原始值
            return self.min_num + peek
    def top(self):
        # write code here
        # 同上述pop相同
        peek = self.stack[-1]
        if peek < 0:
            # 表示栈顶为当前最小值
            return self.min_num
        else:
            # 根据当前最小值和差值计算原始值
            return self.min_num + peek
    def min(self):
        # write code here
        # 直接返回
        return self.min_num




发表于 2021-07-09 22:26:56 回复(0)
Python
wengJJ头像 wengJJ
Python
发现很多同学忽略了题目的要求O（1），例如当你使用Python的min函数时，时间复杂度已经达到O（n）了
我这里的思路也是一个辅助栈的思路：PUSH的时候将min的信息也包含在里面
正常栈：3，-1，2，0
减去当前min值
辅助栈：0，-4，3，1
每次要输出的时候，与min值进行相加即可还原原来的值 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minnum = 0
    def push(self, node):
        # write code here
        if not self.stack:
            self.minnum = node
        self.stack.append(node - self.minnum)
        if node < self.minnum:
            self.minnum = node
    def pop(self):
        # write code here
        num = self.stack.pop()
        if num < 0:
            self.minnum = self.minnum - num
#         return num - self.minnum
    def top(self):
        # write code here
        minnum = self.minnum
        if self.stack[-1] < 0:
            minnum = self.minnum - self.stack[-1]
        return self.stack[-1]+minnum
    def min(self):
        return self.minnum
        # write code here


发表于 2021-06-19 01:55:09 回复(0)
Python
Quinn_5400头像 Quinn_5400
使用辅助栈来存每次推入节点时该节点对应的最小值
stack  3 4 2 3 _3 _2 0
assist 3 3 2 2 _2 _2 0
备注 3代表Push3,_3代表Pop3,辅助栈保持同步

特点:辅助队列assist[-1]一直是最小的,且其本身是递减排序的

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        # data
        self.stack = []
        # min 记录最小值
        self.assist = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if self.assist:
            self.assist.append(node if node < self.assist[-1] else self.assist[-1])
        else:
            self.assist.append(node)
    def pop(self):
        # write code here
        if self.stack:
            self.assist.pop()
            return self.stack.pop()
    def top(self):
        # write code here
        if self.stack:
            return self.stack[-1]
    def min(self):
        # write code here
        if self.assist:
            return self.assist[-1]


发表于 2021-04-26 11:07:43 回复(0)
Python
牛客541273514号头像 牛客541273514号 
class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        # write code here
        self.stack1.append(node)
        if len(self.stack2)==0:
            self.stack2.append(node)
        else:
            if node<self.stack2[-1]:
                self.stack2.append(node)
            else:
                self.stack2.append(self.stack2[-1])
    def pop(self):
        # write code here
        if self.stack1:
            self.stack1.pop()
            self.stack2.pop()
    def top(self):
        # write code here
        if self.stack1:
            return self.res[-1]
        else:
            return None
    def min(self):
        # write code here
        if self.stack2:
            return self.stack2[-1]
        else: return None

发表于 2021-04-18 11:23:15 回复(1)
Python
李peak头像 李peak
python大法直接碾压，O(1)复杂度也满足 
# -*- coding:utf-8 -*-
class Solution:
    stack = []
    mini=None
    def push(self, node):
        self.stack.append(node)
        self.mini = min(self.stack)
    def pop(self):
        x = self.stack.pop()
        self.mini = min(self.stack)
        return x
    def top(self):
        return self.stack[-1]
    def min(self):
        return self.mini


编辑于 2021-03-08 15:26:40 回复(0)
Python
食堂在逃干饭王头像 食堂在逃干饭王
用list模拟栈，再用一个辅助list存储每插入一个值时的栈的最小值的索引即可。 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.tstack = []
        self.mstack = []
    def push(self, node):
        # write code here
        self.tstack.append(node)
        if len(self.mstack) == 0:
            self.mstack.append(0)
        else:
            if node <= self.tstack[self.mstack[-1]]:
                self.mstack.append(len(self.tstack)-1)
            else:
                self.mstack.append(self.mstack[-1])
    def pop(self):
        self.mstack.pop(-1)
        return self.tstack.pop(-1)
    
    def top(self):
        return self.tstack[-1]
    def min(self):
        return self.tstack[self.mstack[-1]]




编辑于 2021-02-09 15:28:24 回复(0)
Python
老和山小学生头像 老和山小学生 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.assistStack = []
    def push(self, node):
        # write code here
        if not self.assistStack&nbs***bsp;node < self.assistStack[-1]:
            self.assistStack.append(node)
        else:
            self.assistStack.append(self.assistStack[-1])
        self.stack.append(node)
    def pop(self):
        # write code here
        if self.stack:
            self.assistStack.pop()
            return self.stack.pop()
    def top(self):
        # write code here
        if self.stack:
            return self.stack[-1]
    def min(self):
        # write code here
        if self.assistStack:
            return self.assistStack[-1]

发表于 2020-10-12 20:19:34 回复(0)
Python
君子不自弃医者不自医头像 君子不自弃医者不自医
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack=[]
        self.assist=[]
    def push(self, node):
        min = self.min()
        if min > node or min==None: 
            self.stack.append(node)
            self.assist.append(node)
        else:
            self.stack.append(node)
    def pop(self):
        if self.stack:
            if self.stack[-1] ==self.assist[-1]:
                self.stack.pop()
                self.assist.pop()
            else:
                self.stack.pop()
    def top(self):
        if self.stack:
            return self.stack[-1]
    def min(self):
        if self.assist:
            return self.assist[-1]
        # write code here
发表于 2020-09-15 16:46:28 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minValue = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if self.minValue:
            if self.minValue[-1] > node:
                self.minValue.append(node)
            else:
                self.minValue.append(self.minValue[-1])
        else:
            self.minValue.append(node)
    def pop(self):
        # write code here
        if not self.stack: 
            return None
        self.minValue.pop()
        return self.stack.pop()
    def top(self):
        # write code here
        if not self.stack: 
            return None
        return self.stack[-1]
    def min(self):
        # write code here
        if not self.minValue:
            return None
        return self.minValue[-1]
用空间换时间，空间多时间复杂度小；空间少时间复杂度大。
发表于 2020-08-05 17:07:16 回复(0)
Python
www_helloworld_cn头像 www_helloworld_cn

利用辅助栈，和当前栈同增减，保证栈顶的数是当前栈中最小的数。
push时：如果当前push的数小于辅助栈栈顶的数，则说明新来的数是最小的，辅助栈push新来的数，否则说明辅助栈栈顶的数更小，辅助栈push辅助栈栈顶的数；
pop时：当前栈弹出一个数，辅助栈也要弹出一个数，保证两个栈高度一样。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s = []
        self.min1 = []
    def push(self, node):
        # write code here
        self.s.append(node)
        if len(self.min1)==0:
            self.min1.append(node)
        else:
            if node<self.min1[-1]:
                self.min1.append(node)
            else:
                self.min1.append(self.min1[-1])
    def pop(self):
        self.s.pop()
        self.min1.pop()
        # write code here
    def top(self):
        if len(self.s) > 0:
            return self.s[-1]
    def min(self):
        if len(self.min1)>0:
            return self.min1[-1]
发表于 2020-08-04 07:57:55 回复(0)
Python
莱布尼兹的n+3阶头像 莱布尼兹的n+3阶 
class Solution:
    def __init__(self):
        self.stack = []
        self.minstack = []
    def push(self, node):
        self.stack.append(node)
        if self.minstack == []:
            self.minstack.append(node)
        else:
            if node <= self.minstack[-1]:
                self.minstack.append(node)
            else:
                self.minstack.append(self.minstack[-1])
    def pop(self):
        self.stack.pop()
        self.minstack.pop()
    def top(self):
        return self.stack[-1]
    def min(self):
        return self.minstack[-1]

发表于 2020-07-29 20:51:48 回复(0)
Python
Kuriyamaaa头像 Kuriyamaaa 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.zhanA=[]
        self.zhanB=[]
        self.zhanC=[]
        self.lenA=0
        self.lenB=0
        self.lenC=0
    def push(self, node):
        self.zhanA.append(node)
        self.lenA+=1
        # write code here
    def pop(self):
        if self.lenA==0:
            return '空栈'
        self.lenA-=1
        return self.zhanA.pop()
        # write code here
    def top(self):
        if self.lenA==0:
            return '空栈'
        return self.zhanA[-1]
    def pushB(self, node):
        self.zhanB.append(node)
        self.lenB+=1
        # write code here
    def popB(self):
        if self.lenB==0:
            return '空栈'
        self.lenB-=1
        return self.zhanB.pop()
        # write code here
    def topB(self):
        if self.lenB==0:
            return '空栈'
        return self.zhanB[-1]
    def pushC(self, node):
        self.zhanC.append(node)
        self.lenC+=1
        # write code here
    def popC(self):
        if self.lenC==0:
            return '空栈'
        self.lenC-=1
        return self.zhanC.pop()
        # write code here
    def topC(self):
        if self.lenC==0:
            return '空栈'
        return self.zhanC[-1]
 
       # write code here
    def min(self):
        self.zhanB=[]
        self.lenB=0
        self.zhanC=[]
        self.lenC=0
        
            
        if self.lenA==0:
            return 'kong'
        if self.lenA==1:
            return self.top()
        lenn=self.lenA
        self.pushC(self.top())
        self.pushB(self.pop())
        for i in range(lenn-1):
            temp=self.pop()
            self.pushC(temp)
            if temp<=self.topB():
                self.pushB(temp)
            else:
                pass
            
        for i in range(self.lenC):
            self.push(self.popC())
        
        
        return self.topB() 
        
                
                
            
            
        
        # write code here

发表于 2020-05-27 15:46:43 回复(0)
Python
谢小橙头像 谢小橙 
class Solution:
    def __init__(self):
        self.stack=[] # 数据栈
        self.min_stack=[] # 辅助栈
    def push(self, node):
        # write code here
        self.stack.append(node)
        if self.min_stack!=[]:
            if self.min_stack[-1]<node:# 新入栈的元素比min_stack栈顶元素大
                self.min_stack.append(self.min_stack[-1])
            else:# 新入栈的元素比min_stack栈顶元素小
                self.min_stack.append(node)
        else:#min_stack为空，直接插入node
            self.min_stack.append(node)
    def pop(self):
        # write code here
        if self.stack!=[]:
            self.min_stack.pop()
            return self.stack.pop()
        else:
            return None
    def top(self):
        # write code here
        if self.stack!=[]:
            return self.stack[-1]
        else:
            return None
    def min(self):
        # write code here
        if self.min_stack!=[]:
            return self.min_stack[-1]
        else:
            return None
引入一个辅助栈，该栈的功能是存入相应数据栈对应位置前最小的栈中数据，同时push和pop随着数据栈进行相应的处理。
编辑于 2020-03-15 10:08:57 回复(0)
Python
朝夕_头像 朝夕_ 
class Solution:
    def __init__(self):
        self.stack,self.min_stack = [],[]
    def push(self, node):
        self.stack.append(node)
        if not self.min_stack&nbs***bsp;node < self.min_stack[-1]:
            self.min_stack.append(node)
        else:
            self.min_stack.append(self.min_stack[-1])
    def pop(self):
        self.min_stack.pop()
        return self.stack.pop()
    def top(self):
        return self.stack[-1]
    def min(self):
        return self.min_stack[-1]

发表于 2020-03-01 15:04:03 回复(0)
Python
牛客447097232号头像 牛客447097232号 
"""
空间换时间，每次入栈的时候保存min作为附件信息
"""
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []

    def push(self, node):
        if not self.min():
            self.stack.append((node,node))
        else :
            if node < self.min():
                self.stack.append((node, node))
            else:
                self.stack.append((node,self.min()))
        print(self.stack)

    def pop(self):
        if len(self.stack) == 0:
            return None
        self.stack.pop()

    def top(self):
        if len(self.stack) == 0:
            return None
        return self.stack[-1][1]

    def min(self):
        if len(self.stack) == 0:
            return None
        return self.top()


s = Solution()
s.push(3)
s.min()
s.push(4)
print(s.min())
发表于 2020-02-27 17:22:24 回复(0)
Python
牛客882602551号头像 牛客882602551号
思路：栈stack保存数据，辅助栈assist保存依次入栈最小的数
stack中依次入栈，6，5，8，4，3，9
assist依次入栈，6，5，4，3
每次入栈的时候，如果入栈的元素比assist中的栈顶元素小或等于则入栈，否则不如栈。 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []    #数据栈
        self.assist = []   #辅助栈
    def push(self, node):
        # write code here
        min = self.min()             #得到栈中元素的最小值
        if min > node&nbs***bsp;not min:    #若待入栈的元素值小于栈中最小值或栈为空时
            self.stack.append(node)  #将这个元素分别压入数据栈和辅助栈
            self.assist.append(node)
        else:
            self.stack.append(node)  #否则只将这个元素压入数据栈
    def pop(self):
        # write code here
        if self.stack:
            if self.stack[-1] == self.assist[-1]:  #若数据栈和辅助栈的栈顶的元素值相等
                self.stack.pop()                   #则分别将这两个栈的栈顶元素弹出
                self.assist.pop()
            else:
                self.stack.pop()   #否则只弹出数据栈的栈顶元素
    def top(self):
        # write code here
        if self.stack:
            return self.stack[-1]  #返回数据栈的栈顶元素
    def min(self):
        # write code here
        if self.assist:
            return self.assist[-1] #返回顶层元素，即最小值



编辑于 2019-12-22 13:57:06 回复(0)
Python
黄沙遮天头像 黄沙遮天 
class Solution:
    def __init__(self):
        self.list1=[]
        self.top1=-1
    def push(self, node):
        # write code here
        self.list1.append(node)
        self.top1+=1
    def pop(self):
        # write code here
        if self.top1==-1:
            return None
        else:
            a=self.list1.pop()
            self.top1=self.top1-1
            return a
    def top(self):
        # write code here
        if self.top1!=-1:
            return self.list1[-1]
        else:
            return None
    def min(self):
        # write code here
        min=self.top()
        for i in self.list1[::-1]:
            if min>i:
                min=i
        return min
这个题很简单，问题就是了解stack结构，重点就是定义列表和栈的top，另外对于min阶段的话就是遍历了，
不要把元素跳出，因为他每次都是计算整个栈的最小值

发表于 2019-12-10 21:46:57 回复(0)
Python
吕营头像 吕营

Python 

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minValue = []    
    def push(self, node):
        # write code here
        self.stack.append(node)
        if self.minValue:
            if self.minValue[-1]>node:
                self.minValue.append(node)
            else:
                self.minValue.append(self.minValue[-1])
        else:
            self.minValue.append(node)
                
    def pop(self):
        # write code here
        if self.stack ==[]:
            return None
        self.minValue.pop()
        return self.stack.pop()
    def top(self):
        # write code here
        if self.stack  ==[]:
            return None
        return self.stack[-1]
    def min(self):
        # write code here
        if self.minValue == [] :
            return None 
        else:
            return self.minValue[-1]


发表于 2019-12-09 12:37:47 回复(0)
Python
天山剑客头像 天山剑客 
# -*- coding:utf-8 -*-
# 解题思路：使用另外一个栈2保存当前栈1中的最小元素
# 入栈时如果栈2为空，那么元素同时入栈1和2
# 入栈时如果栈2不空，并且元素比栈2栈顶的元素小，那么同时入栈1和2
# 入栈时如果栈2不空，并且元素比栈2栈顶的元素大，那么只入栈1，因为栈2顶部元素在栈1中，一定比它小
# 出栈时如果栈1不空，栈1顶部元素和栈2顶部元素相等，那么同时出栈1和栈2
# 栈1顶部为当前栈顶元素
# 栈2顶部为栈1中的最小元素
class Solution:
    def __init__(self):
        self.stack1 = list()
        self.stack2 = list()
      
    def push(self, node):
        # write code here
        self.stack1.append(node)
        
        if not self.stack2:
          self.stack2.append(node)
          
        if self.stack2 and node < self.stack2[-1]:
          self.stack2.append(node)
          
    def pop(self):
        # write code here
        if self.stack1:
          if self.stack1[-1] == self.stack2[-1]:
            self.stack1.pop()
            self.stack2.pop()
          else:
            self.stack1.pop()
            
    def top(self):
        # write code here
        if self.stack1:
          return self.stack1[-1]
          
    def min(self):
        # write code here
        if self.stack2:
          return self.stack2[-1]
        

发表于 2019-12-07 20:33:49 回复(0)
提交观点

问题信息

栈
难度：
68条回答 153467浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号