首页 > 试题广场 >

包含min函数的栈

[编程题]包含min函数的栈
  • 热度指数：649770 时间限制：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)
Java
神奇的安迪面试中头像 神奇的安迪面试中 
import java.util.*;
import java.util.Stack;

public class Solution {
    
    Stack<Integer> stack=new Stack<Integer>();
    
    public void push(int node) {
        stack.push(node);
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        Stack<Integer> stackTemp= (Stack)stack.clone();
        int res=Integer.MAX_VALUE;
        while(stackTemp.size()!=0){
            if(stackTemp.peek()<res) res=stackTemp.pop();
            else stackTemp.pop();
        }
        return res;
        
    }
}

发表于 2024-04-24 14:29:53 回复(0)
Java
陌路丶花开头像 陌路丶花开
这道题是不是也可以用List来模拟呢？
import java.util.*;
import java.util.Stack;

public class Solution {
    List<Integer> lists = new ArrayList<>();
    int size = 0;

    
    public void push(int node) {
        lists.add(node);
        size++;
    }
    
    public void pop() {
        lists.get(size-1);
        lists.remove(size-1);
        size--;
    }
    
    public int top() {
        return lists.get(size-1);
    }
    
    public int min() {
        int min = Integer.MAX_VALUE;
        for(int item : lists){
            min = Math.min(min, item);
        }
        return min;
    }
}


发表于 2024-04-22 20:29:20 回复(0)
Java
你好，侦探先生头像 你好，侦探先生 
import java.util.*;
import java.util.Stack;

public class Solution {
    Stack stack1 = new Stack<Integer>();
    Stack stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public void pop() {
        Iterator iterator = stack1.iterator();
        while (iterator.hasNext()) {
            stack2.push(iterator.next());
        }
        stack2.pop();
    }
    public int top() {
        return Integer.parseInt(stack1.peek().toString());
    }

    public int min() {
        ArrayList<Integer> integersList = new ArrayList<>();
        Iterator iterator = stack1.iterator();
        while (iterator.hasNext()) {
            integersList.add(Integer.valueOf(iterator.next().toString()));
        }
        return Collections.min(integersList);
    }
}

编辑于 2024-03-26 15:37:53 回复(0)
Java
WLDecade头像 WLDecade 
import java.util.*;

public class Solution {

    // 优先队列 + 栈
    PriorityQueue<Integer> queue = new PriorityQueue<>(300);
    Stack<Integer> stack = new Stack<>();
    public void push(int node) {
        queue.add(node);
        stack.push(node);
    }
    
    public void pop() {
        queue.remove(stack.pop());
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return queue.peek();
        
    }
}
被自己逗乐了，过于偷懒hhh
编辑于 2024-02-27 20:29:41 回复(0)
Java
15zed头像 15zed 
public class Solution {

    Stack<Integer> stack = new Stack<>();

    public void push(int node) {
        stack.add(node);
    }

    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        Integer[] array = stack.toArray(new Integer[stack.size()]);
        Arrays.sort(array);
        return array[0];
    }
}

编辑于 2024-01-06 18:43:22 回复(0)
Java
李克雷头像 李克雷 
public class Solution {

    Stack<Integer> stack = new Stack<>();

    Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        stack.push(node);
        if (minStack.isEmpty()) {
            minStack.push(node);
            return;
        }
        minStack.push(Math.min(node, minStack.peek()));
    }

    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop() ;
            minStack.pop();
        }
    }

    public int top() {
        if (stack.isEmpty()) {
            throw new RuntimeException("can not get top element from an empty stack");
        }
        return stack.peek();
    }

    public int min() {
        if (stack.isEmpty()) {
            throw new RuntimeException("can not get min element from an empty stack");
        }
        return minStack.peek();
    }

}

发表于 2023-10-24 17:58:50 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public class Solution {
    //用两个栈控制
    Stack<Integer> st1=new Stack<>();
    Stack<Integer> st2=new Stack<>();

    
    public void push(int node) {
        st1.push(node);
        if(st2.isEmpty()||(node<st2.peek())){
            st2.push(node);//加入元素
        }else{
            st2.push(st2.peek());//重复加入栈顶
        }
    }
    
    public void pop() {  //不需要返回值
        st1.pop();
        st2.pop();
        
    }
    
    public int top() {
        return st1.peek();
    }
    
    public int min() {
        return st2.peek();   
    }
}

发表于 2023-07-19 10:38:02 回复(0)
Java
抓住努力的尾巴头像 抓住努力的尾巴 
import java.util.*;
import java.util.Stack;

public class Solution {

    public Stack<Integer> sta = new Stack<>();
    public Stack<Integer> help = new Stack<>();


    public void push(int node) {
        sta.push(node);
        if(help.isEmpty()) {
            help.push(node);
        } else {
            if(help.peek() <= node) {
                help.push(help.peek());
            } else {
                help.push(node);
            }
        }
    }

    public void pop() {
        sta.pop();
        help.pop();
    }

    public int top() {
        return sta.peek();
    }

    public int min() {
        return help.peek();
    }
}
发表于 2023-07-15 16:12:55 回复(0)
Java
Hadoopdoop头像 Hadoopdoop 
public class Solution {
    Stack<Integer> stack = new Stack<>();

    public void push(int node) {
        stack.push(node);
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        Stack<Integer> newStack = new Stack<>();
        int min = Integer.MAX_VALUE;
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            if (pop < min) min = pop;
            newStack.push(pop);
        }
        while (!newStack.isEmpty()) {
            stack.push(newStack.pop());
        }
        return min;
    }
}

发表于 2023-03-09 13:50:15 回复(0)
Java
牛客928243408号头像 牛客928243408号
Java 注意 Integer 类型的 == 比较， 会有坑， 应该使用 equals, 或者转为 int 比较。 本题中， 可以使用 <= 通过。
发表于 2022-12-20 22:05:55 回复(0)
Java
dynamo1头像 dynamo1 
import java.util.Stack;

public class Solution {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> min = new Stack<>();

    public void push(int node) {
        stack.push(node);
        if (min.isEmpty()) {
            min.push(node);
            return;
        }
        int peek = min.peek();
        if (node < peek) {
            min.push(node);
        }else {
            min.push(peek);
        }
        return;
        
    }
    
    public void pop() {
        stack.pop();
        min.pop();
    }
    
    public int top() {
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.peek();
    }
    
    public int min() {
         return min.peek();
    }
}

发表于 2022-12-04 17:01:52 回复(0)
Java
键盘都敲坏了.头像 键盘都敲坏了. 
public class Solution {

    
    // 正常存值的栈
    Stack<Integer> stack1 = new Stack<Integer>();
    // 储存最小值的栈
    Stack<Integer> minStack = new Stack<Integer>();
    public void push(int node) {
        stack1.push(node); // 存储node

        // 如果minStack为空，直接存入node
        if(minStack.isEmpty()) minStack.push(node);
        // 如果不为空时，本次node 和minStack栈顶元素比较大小，minStack插入这两个数的最小值
        else minStack.push(Math.min(node,minStack.get(minStack.size() - 1)));

        // 对上面代码举例
        // stack1 依次存入          1 2 3 4 -1
        // minStack 实际存入的值为:  1 1 1 1 -1
        // minStack每次存的值 都是相对于stack1中 所有元素的最小值
    }

    public void pop() {
        // 弹出时，必须两个一起弹出
        stack1.pop(); 
        minStack.pop();
    }

    public int top() {
       return stack1.get(stack1.size() - 1);
    }

    public int min() {
        return minStack.get(minStack.size() - 1);
    }
}

发表于 2022-11-10 15:56:17 回复(0)
Java
胆小的小师弟还是想躺平头像 胆小的小师弟还是想躺平
import java.util.Stack;
import java.util.*;
public class Solution {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    
    public void push(int node) {
        stack1.push(node);
        
    }
    
    public void pop() {
        stack1.pop();
        
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        int temp=stack1.peek();
        while(!stack1.isEmpty()){
           temp=Math.min(temp,stack1.peek());
           stack2.push(stack1.pop()); 
        }
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        return temp;
    }
}a

发表于 2022-11-07 19:19:41 回复(0)
Java
牛客461316693号头像 牛客461316693号 
import java.util.*;
import java.util.Stack;

public class Solution {

    
    private LinkedList<Integer> list = null;
    private int min;

    public Solution() {
        list = new LinkedList<>();
        min = 0;
    }

    public void push(int x) {
        if (list.isEmpty()) {
            min = x;
        }
        if (min > x) {
            min = x;
        }
        list.push(x);
    }

    public void pop() {
        if (list.isEmpty()) {
            return;
        }
        Integer pop = list.pop();
                //如果弹出的和最小值一样，遍历剩下数组，查找最新最小值，
        if (pop == min) {
            if (list.isEmpty()) {
                return;
            }
            min = list.get(0);
            int length = list.size();
            for (int i = 1; i < length; i++) {
                if (list.get(i) < min) {
                    min = list.get(i);
                }
            }
        }
    }

    public int top() {
        return list.peek();
    }

    public int min() {
        return min;
    }
}

发表于 2022-08-17 11:23:19 回复(0)
Java
牛客262519728号头像 牛客262519728号 
import java.util.*;
import java.util.Stack;

public class Solution {
    ArrayList<Integer> s = new ArrayList<>();
    
    public void push(int node) {
        s.add(node);
    }
    
    public void pop() {
        s.remove(s.size()-1);
    }
    
    public int top() {
        return s.get(s.size()-1);
    }
    
    public int min() {
        return Collections.min(s);
    }
}

发表于 2022-08-14 18:19:55 回复(1)
Java
yxjing头像 yxjing 
import java.util.*;
import java.util.Stack;

public class Solution {

    Stack<Integer> stack1=new Stack<Integer>();
    Stack<Integer> stack2=new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public void pop() {
        if(!stack1.isEmpty()){
            stack1.pop();
        }
    }
    
    public int top() {
        int result=-1;
        if(!stack1.isEmpty()){
            result=stack1.peek();
        }
        return result;
        
    }
    
    public int min() {
        Stack<Integer> stack3=new Stack<Integer>();
        while(!stack1.isEmpty()){
            int value=stack1.pop();
            stack2.push(value);//因为这里动了stack1!!!
            stack3.push(value);   
        }
        while(!stack3.isEmpty()){
            stack1.push(stack3.pop());//将stack1复原
        }
        //min是对stack2操作
        int result=stack2.peek();
        while(!stack2.isEmpty()){
            int value=stack2.pop();
            if(value<result){
                result=value;
            }
        }
        return result;
    }
}

发表于 2022-07-29 13:33:06 回复(0)
Java
理应前行头像 理应前行 
import java.util.*;
import java.util.Stack;

public class Solution {
    Stack<Integer> stack = new Stack<Integer>();
    List<Integer> list=new ArrayList<Integer>();
    public void push(int node) {
        list.add(node);
        stack.push(node);
    }
    
    public void pop() {
        list.remove(stack.peek());
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        Collections.sort(list);
        return list.get(0);
    }
}

发表于 2022-07-22 14:57:00 回复(0)
Java
雨き头像 雨き
有没有大佬看看我这个为什么会有个用例不对
发表于 2022-07-15 16:42:05 回复(0)
提交观点

问题信息

栈
难度：
277条回答 153646浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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