首页 > 试题广场 >

包含min函数的栈

[编程题]包含min函数的栈
  • 热度指数：657860 时间限制：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 3
故乡的雨头像 故乡的雨 
class Solution:
    def __init__(self) -> None:
        self.stack = []
        self.min_value = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.min_value:
            self.min_value.append(node)
        else:
            self.min_value.append(min(self.min_value[-1], node))
    def pop(self):
        # write code here
        self.stack.pop()
        self.min_value.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.min_value[-1]
发表于 2023-09-07 09:35:32 回复(0)
Python 3
pzq头像 pzq 
class Solution:
    stack = []
     
    def push(self, node):
        self.stack.append(node)
 
    def pop(self):
        self.stack.pop(-1)
 
    def top(self):
        return self.stack[-1]
 
    def min(self):
        return min(self.stack)

# 方法二：官方原意
class Solution:
    stack1 = []
    stack2 = [] # 保存最小值

    def push(self, node):
        self.stack1.append(node)
        if self.stack2 == []:
            self.stack2.append(node)
            return
        if node < self.stack2[-1]:
            self.stack2.append(node)
            return
        self.stack2.append(self.stack2[-1])

    def pop(self):
        self.stack1.pop(-1)
        self.stack2.pop(-1)

    def top(self):
        return self.stack1[-1]

    def min(self):
        return self.stack2[-1]

发表于 2023-06-15 00:53:18 回复(0)
Python 3
JianYue头像 JianYue 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []

    def push(self, node):
        self.stack.append(node)

    def pop(self):
        return self.stack.pop()

    def top(self):
        return self.stack[-1]

    def min(self):
        m = self.stack[0]
        for i in range(1, len(self.stack)):
            if m > self.stack[i]:
                m = self.stack[i]
        return m

发表于 2022-09-14 18:19:49 回复(0)
Python 3
风软一江山头像 风软一江山 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.stack_min = []
        
    def push(self, node):
        self.stack.append(node)
        if not self.stack_min:
            self.stack_min.append(node)
        elif node < self.stack_min[-1]:
            self.stack_min.append(node)
        else:
            self.stack_min.append(self.stack_min[-1])
        
    def pop(self):
        self.stack_min.pop()
        return self.stack.pop()
        
    def top(self):
        return self.stack[-1]
        
    def min(self):
        return self.stack_min[-1]

发表于 2022-07-29 12:55:06 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    def __init__(self):
        self.s1 = []
        self.s2 = []
    def push(self, node):
        self.s1.append(node)
        if len(self.s2) == 0 or self.s2[-1] > node:
            self.s2.append(node)
        else:
            self.s2.append(self.s2[-1])
    def pop(self):
        self.s2.pop()
        self.s1.pop()
    def top(self):
        return self.s1[-1]
    def min(self):
        return self.s2[-1]
发表于 2022-05-06 16:40:57 回复(0)
Python 3
牛客568079703号头像 牛客568079703号
python3 双列表实现  所有操作时间复杂度O(1),空间复杂度O(n) 
class Solution:
    stack=[]
    stack_min=[float('inf')]  
    def push(self, node):
        # write code here
        self.stack.append(node)
        self.stack_min.append(min(self.stack_min[-1],node))  
    def pop(self):
        # write code here
        self.stack.pop()
        self.stack_min.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.stack_min[-1]


发表于 2022-04-29 15:55:44 回复(0)
Python 3
小小小小燃头像 小小小小燃 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.data = []
        
    def push(self, node):
        # write code here
        self.data = [node] + self.data
        
    def pop(self):
        # write code here
        if self.check_null(): return []
        
        self.data = self.data[1:]
        
        
    def top(self):
        # write code here
        if self.check_null(): return []
        
        return self.data[0]
        
        
    def min(self):
        # write code here
        if self.check_null(): return []
            
        return min(self.data)
    
    def check_null(self):
        if len(self.data) == 0:
            return True
        else:
            return False

发表于 2022-04-09 22:17:50 回复(0)
Python 3
一只兔子的奇幻之旅头像 一只兔子的奇幻之旅 
class Solution:
    def __init__(self) -> None:
        self.sk1=[]
        self.sk2=[]
    def push(self, node):
        self.sk1.append(node)
        if len(self.sk2)==0&nbs***bsp;node <=self.sk2[-1]:
            self.sk2.append(node)
        else:
            self.sk2.append(self.sk2[-1])
    def pop(self):
        self.sk2.pop()
        return self.sk1.pop()
    def top(self):
        return self.sk1[-1]
    def min(self):
        return self.sk2[-1]

发表于 2022-04-05 09:07:42 回复(0)
Python 3
梦幻泡影oO头像 梦幻泡影oO

Python

class Solution:

    s = []
    t = []

    def push(self, node):
        self.s.append(node)
        if not self.t or self.t[-1] >= node:
            self.t.append(node)

    def pop(self):
        if self.s.pop() == self.t[-1]:
            self.t.pop()

    def top(self):
        return self.s[-1]

    def min(self):
        return self.t[-1]
发表于 2022-03-22 14:13:26 回复(0)
Python 3
握着我的抱枕头像 握着我的抱枕

python 利用辅助栈实现

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.A,self.B=[],[]
    def push(self, node):
        # write code here
        self.A.append(node)
        if not self.B or self.B[-1]>=node:
            self.B.append(node)
    def pop(self):
        # write code here
        if self.A.pop()==self.B[-1]:
            self.B.pop()
    def top(self):
        # write code here
        return self.A[-1]
    def min(self):
        # write code here
        return self.B[-1]
发表于 2021-11-07 23:26:54 回复(0)
Python 3
归海迎夏头像 归海迎夏
class Solution:
    def __init__(self):
        self.array = []
    def push(self, node):
        # write code here
        self.array.append(node)
    def pop(self):
        # write code here
        self.array.pop()
    def top(self):
        # write code here
        return self.array[-1]
    def min(self):
        # write code here
        return min(self.array)
发表于 2021-10-09 02:20:47 回复(0)
Python 3
season1blue头像 season1blue 
# -*- coding:utf-8 -*-
class Solution:
    stack = []
    minstack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if len(self.minstack)==0:
            self.minstack.append(node)
        else:
            val=self.minstack[-1]
            if node>val:
                self.minstack.append(val)
            else:
                self.minstack.append(node)
            
                

        
    def pop(self):
        # write code here
        result = self.stack[-1]
        del self.stack[-1]
        del self.minstack[-1]
        return result

    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        return self.minstack[-1]


发表于 2021-09-01 15:27:44 回复(0)
Python 3
三水123头像 三水123 
class Solution:
    def __init__(self):
        self.stack = []
        self.assist = []
    def push(self, node):
        # write code here
        min = self.min()
        if not min&nbs***bsp;node<min:
            self.assist.append(node)
        else:
            self.assist.append(min)
        self.stack.append(node)
    def pop(self):
        # write code here
        if self.stack:
            self.assist.pop(-1)
            self.stack.pop(-1)
    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-08-13 14:16:22 回复(0)
Python 3
阿司匹林Yo头像 阿司匹林Yo 
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)

    def pop(self):
        num = self.stack.pop()
        if num == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def min(self):
        return self.min_stack[-1]

发表于 2021-08-12 15:23:42 回复(0)
Python 3
tantantansq头像 tantantansq 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack=[]
        self.mins=[] 
        
    def push(self, node):
        # write code here
        self.stack.append(node) 
        if len(self.mins)>0:
            self.mins.append(min(node,self.mins[-1]))
        else:
            self.mins.append(node)
        
    def pop(self):
        # write code here
        if len(self.stack)>0:
            self.stack.pop()
            self.mins.pop()

    def top(self):
        if len(self.stack)>0:
            return self.stack[-1]
        else:
            return None
        # write code here
    def min(self):
        # write code here
        if len(self.mins)>0:
            return self.mins[-1]
        else:
            return None

发表于 2021-08-08 19:58:18 回复(0)
提交观点

问题信息

栈
难度：
19条回答 155583浏览

热门推荐

通过挑战的用户

查看代码

相关试题

包含min函数的栈

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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