包含min函數(shù)的棧

考點：棧

題目描述

定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復(fù)雜度應(yīng)為O（1））。

代碼格式

import java.util.Stack;

public class Solution {    
    public void push(int node) {        
    } 
    public void pop() {        
    } 
    public int top() {        
    }    
    public int min() {    
    }
}

測試用例

image.png

知識點

java中的棧Stack的基本使用和應(yīng)用
棧定義　　棧是一種只能在一端進(jìn)行插入或刪除操作的線性表。（先進(jìn)后出表）
java中的Stack繼承Vector
實例化 Stack stack=new Stack();
基本使用:
判斷是否為空stack.empty()
取棧頂值（不出棧）stack.peek()
進(jìn)棧stack.push(Object);
出棧stack.pop();

解題一-兩個棧

1.思路
棧stack1保存數(shù)據(jù)，輔助棧stack2保存依次入棧最小的數(shù)
stack1中依次入棧，6，5，8，4，3，9
stack2依次入棧，6，5，5，4，3，3
每次入棧的時候，如果入棧的元素比stack2中的棧頂元素小或等于則入棧，否則不入棧。
2.代碼

import java.util.Stack;

public class Solution {
    private Stack<Integer> stack1=new Stack<>();
    private Stack<Integer> stack2=new Stack<>();
    
    public void push(int node) {
        stack1.push(node);
        if(stack2.empty()){
            stack2.push(node);
        }else{
            if(node <= stack2.peek()){
                stack2.push(node);
            }else{
                stack2.push(stack2.peek());
            }
        }
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
 
    public int top() {
        return stack1.peek();
    }
 
    public int min() {
        return stack2.peek();
    }
}

解題二-一個棧

1.思路
在棧中需要保留冗余的曾經(jīng)的最小值，這樣能夠比較方便到找到當(dāng)前的此小值
2.代碼

//https://www.nowcoder.com/questionTerminal/4c776177d2c04c2494f2555c9fcc1e49?answerType=1&f=discussion
//?？途W(wǎng)

import java.util.Stack;
 
public class Solution {
 
    //需要這樣寫來初始化stack，不然會報空指針push的時候
    private static Stack<Integer> stack = new Stack<Integer>();
    private static Integer minElement = Integer.MAX_VALUE;
 
    public void push(int node) {
        if(stack.empty()){
            minElement = node;
            stack.push(node);
        }else{
            if(node <= minElement){
                stack.push(minElement);//在push更小的值時需要保留在此值之前的最小值
                minElement = node;
            }
            stack.push(node);
        }
    }
 
    public void pop() {
 
       //增加最后一個元素以及棧為空時候的檢測
        if(stack.size() == 0)return;
        if( minElement == stack.peek()){
            if(stack.size() >1){
                stack.pop();
                minElement = stack.peek();
            }else{
                minElement = Integer.MAX_VALUE;
            }
 
        }
        stack.pop();
    }
 
    public int top() {
        return stack.peek();
    }
 
    public int min() {
        return minElement;
    }
}