首页 > 试题广场 >

包含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)
Java
研究生找工作ing头像 研究生找工作ing
大佬们，这哪里有问题？我觉得我的输出应该是-1024 -1024 512
import java.util.*;
import java.util.Stack;

public class Solution {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public void push(int node) {
        stack1.push(node);
        if (stack2.isEmpty() || stack2.peek() >= node) {
            stack2.push(node);
        }
    }

    public void pop() {
        if (stack1.peek() == stack2.peek()) {
            stack2.pop();
        }
        stack1.pop();
    }

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

    public int min() {
        return stack2.peek();
    }
}


发表于 2024-09-15 22:24:58 回复(0)
Java
牛客499848474号头像 牛客499848474号
import java.util.*;
import java.util.Stack;

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() {
        int min = Integer.MAX_VALUE;
        for(Integer i : stack){
            if(i < min){
                min = i;
            }
        }
        return min;
    }
}

发表于 2024-09-15 22:21:18 回复(1)
Java
牛客348570162号头像 牛客348570162号 
public class Solution {
    private int[] stack = new int[300];
    private int[] stack2 = new int[300];
    private int top = 0;

    public void push(int node) {
        stack[top] = node;
        if(top == 0 || stack2[top-1] > node){
            stack2[top] = node;
        }else{
            stack2[top] = stack2[top-1];
        }
        top++;
    }
    
    public void pop() {
        top--;
    }
    
    public int top() {
        return stack[top-1];
    }
    
    public int min() {
        return stack2[top-1];
    }
}

发表于 2024-08-29 15:08:16 回复(0)
Java
人间水长东头像 人间水长东 
import java.util.*;
import java.util.Stack;

public class Solution {
    // 用于存储内容的栈
    Stack<Integer> nodeStack = new Stack<>();
    // 用于【同步】存储当前栈中最小值的栈
    Stack<Integer> minStack = new Stack<>();
    
    // 入栈
    public void push(int node) {
        // 两个栈要同步
        
        // 入nodeStack
        nodeStack.push(node);

        // 入minStack
        if (minStack.isEmpty()) {
            // 如果minStack空，则无需比较
            minStack.push(node);
        }
        // 如果minStack非空，则需要比较，将较小的压入minStack
        int min = Math.min(node, minStack.peek());
        minStack.push(min);
    }
    
    // 出栈（只弹出不返回）
    public void pop() {
        // 两个栈要同步
        nodeStack.pop();
        minStack.pop();
    }
    
    // 获得栈顶元素（只返回不弹出）
    public int top() {
        return nodeStack.peek();
    }
    
    // 获得栈中最小元素（只返回不弹出）
    public int min() {
        return minStack.peek();
    }
}

发表于 2024-08-07 20:28:44 回复(0)
Java
୧⍢⃝୨头像 ୧⍢⃝୨ 
import java.util.*;

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

    public void push(int node) {
        stack1.push(node);
        Stack<Integer> temp = new Stack<>();
        if (!stack2.isEmpty()) {
            if (stack2.peek() >= node) {
                stack2.push(node);
            } else {
                while (!stack2.isEmpty() && stack2.peek() < node) {
                    temp.push(stack2.pop());
                }
                stack2.push(node);
                while (!temp.isEmpty()) {
                    stack2.push(temp.pop());
                }
            }
        } else {
            stack2.push(node);
        }
    }

    public void pop() {
        int val = stack1.pop();
        Stack<Integer> temp = new Stack<>();
        while (stack2.peek() != val && !stack2.isEmpty()) {
            temp.push(stack2.pop());
        }
        stack2.pop();
        while (!temp.isEmpty()) {
            stack2.push(temp.pop());
        }
    }

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

    public int min() {
        int val = stack2.peek();
        return val;
    }
}
发表于 2024-08-02 15:48:11 回复(0)
Java
芒果干201809211642503头像 芒果干201809211642503 
import java.util.Stack
import java.util.Arrays

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param value int整型 
        * @return 无
    */
    val s = Stack<Int>()
    var elements: IntArray = IntArray(10)
    var min = Int.MAX_VALUE
    var head = -1
    
    fun push(value: Int) {
        // write code here
        if(elements.size * 0.8 < head) {
            elements = Arrays.copyOf(elements, elements.size*2)
        }
        elements[++head] = value
        if(value < min) {
            min = value
        } 
        s.push(min)
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param 无 
        * @return 无
    */
    fun pop() {
        // write code here
        if(head >= 0) {
            s.pop()
            head--
            min = s.peek()
        }
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param 无 
        * @return int整型
    */
    fun top(): Int {
        // write code here
        return if(head >=0 ) elements[head] else throw RuntimeException("stack is empty")
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param 无 
        * @return int整型
    */
    fun min(): Int {
        // write code here
        
        return s.peek()
    }
}


发表于 2024-07-11 15:50:57 回复(0)
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)
提交观点

问题信息

栈
难度：
283条回答 155580浏览

热门推荐

通过挑战的用户

查看代码

相关试题

包含min函数的栈

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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