21_包含min函数的栈

亦凉 2022-06-07 02:47 155阅读 0赞

> **题目：**定义一个栈的数据结构（有min、push、pop函数），请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中，调用min、push、pop的时间复杂度都为O(1)。
> 
> **思路：**每次往数据栈压入一个数据，就把数据栈中的最小值都保存起来，存放到另一个辅助栈。这样就能保证辅助栈的栈顶一直都是最小元素。当有元素从数据栈弹出后，也弹出辅助栈的栈顶元素，此时辅助栈的新栈顶也是下一个最小值。

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Stack;
    
    class MinInStack{
        private Stack<Integer> dataStack;//数据栈
        private Stack<Integer> minStack;//最小栈
    
        public MinInStack(){
            dataStack = new Stack<Integer>();
            minStack = new Stack<Integer>();
        }
    
        public void push(int val){
            dataStack.push(val);    
            if(minStack.isEmpty())
                minStack.push(val);
            else{
                int min = minStack.peek();
                if(val < min)
                    minStack.push(val);
                else
                    minStack.push(min);
            }
        }
    
        public void pop(){
            if(!dataStack.isEmpty() && !minStack.isEmpty()){
                // 数据栈弹出一个元素，辅助栈也弹出一个
                dataStack.pop();
                minStack.pop();
            }
        }
    
        public Integer min(){
            return minStack.peek();
        }
    }
    
    public class Solution{
        public static void main(String[] args) throws IOException {
            System.out.println("请依次输入栈元素（空格隔开）：");
            BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
            String xString = bf.readLine();
            if(xString.equals("")){
                System.out.println("输入错误！");
                return;
            }
    
            String[] num = xString.split(" ");
            int[] nums = new int[num.length];
    
            MinInStack stack =new MinInStack();
            for(int i = 0;i<num.length;i++){
                nums[i] = Integer.parseInt(num[i]);
                stack.push(nums[i]);
            }
    
            System.out.println("栈内元素最小值为："+stack.min());
            stack.pop();
            System.out.println("弹出栈顶元素后最小值为："+stack.min());
        }   
    }

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220607/2eb199158c96445890871427ba1bd665.png