題目描述

定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)。

代碼實現(xiàn)

import java.util.Stack;

public class Solution {

    Stack<Integer> stack = new Stack();
    Stack<Integer> min = new Stack();
    
    public void push(int node) {
        stack.push(node);
        if(min.isEmpty() || node <= min.peek())
            min.push(node);
        else
            min.push(min.peek());
    }
    
    public void pop() {
        stack.pop();
        min.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return min.peek();
    }
}

主要思路

1、這道題需要用到兩個棧，一個是數(shù)據(jù)棧，一個是輔助棧
2、每次入棧的時候，輔助棧如果是空的，或者本次入棧的數(shù)據(jù)不大于棧頂，直接入棧，比如2,1,1（數(shù)據(jù)棧）和2,1,1（輔助棧）；否則壓入的是當(dāng)前棧頂?shù)膹?fù)制值，比如2,3,4（數(shù)據(jù)棧）和2,2,2（輔助棧），從而保證數(shù)據(jù)棧里面的最小值永遠在輔助棧的棧頂
3、需要注意的是，實例化棧的時候，一定要傳入一個泛型參數(shù)（本題中的棧存儲的只能是int類型的值），否則比較大小的時候會出錯（node <= min.peek()）
4、訪問棧頂元素用peek方法，而不是top方法