示例

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

思路

請(qǐng)參考設(shè)計(jì)一getMin的棧

代碼演示

package com.itz.stackAndQueue;

import java.util.Stack;

/**
 * 設(shè)計(jì)一個(gè)支持 push，pop，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
 * <p>
 * push(x) -- 將元素 x 推入棧中。
 * pop() -- 刪除棧頂?shù)脑亍? * top() -- 獲取棧頂元素。
 * getMin() -- 檢索棧中的最小元素。
 * 示例:
 * <p>
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.getMin();   --> 返回 -2.
 * <p>
 * 來源：力扣（LeetCode）
 * 鏈接：https://leetcode-cn.com/problems/min-stack
 * 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
 */

/**
 * 執(zhí)行用時(shí) :
 * 8 ms
 * , 在所有 java 提交中擊敗了
 * 100.00%
 * 的用戶
 * 內(nèi)存消耗 :
 * 40.2 MB
 * , 在所有 java 提交中擊敗了
 * 95.58%
 * 的用戶
 */
public class MinStack {

    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }

    public void push(int x) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(x);
        } else if (x <= this.getMin()) {
            this.stackMin.push(x);
        }
        this.stackData.push(x);
    }

    public void pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("你沒有添加數(shù)據(jù)");
        }

        if (stackData.pop() == this.getMin()) {
            this.stackMin.pop();
        }
    }

    public int top() {

        return stackData.peek();
    }

    public int getMin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("你沒有添加數(shù)據(jù)");
        }
        return this.stackMin.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

總結(jié)：

本題有兩種方案設(shè)計(jì)一getMin的棧 兩種方案的時(shí)間復(fù)雜度和空間復(fù)雜度都分別是O(1)、O(n)，只是方法一：在壓入的時(shí)候稍微省空間、但彈出的時(shí)候稍微費(fèi)時(shí)間，方案二 在壓入的時(shí)候稍微費(fèi)空間、但彈出的時(shí)候稍微省時(shí)間。