劍指 Offer 30. 包含min函數的棧

• 2021 年 8 月 9 日
• 筆記
• 劍指Offer

劍指 Offer 30. 包含min函數的棧

定義棧的數據結構，請在該類型中實現一個能夠得到棧的最小元素的 min 函數在該棧中，調用 min、push 及 pop 的時間複雜度都是 O(1)。

示例:

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

提示：

各函數的調用總次數不超過 20000 次

做題思路：

這道題主要是要了解到藉助輔助棧，然後依次把minStack中的數值依次非嚴格排序放在輔助棧則棧minStack最小的值始終對應着輔助棧棧頂元素。

public class Solution {

        Stack<Integer> a = new Stack<>();
        Stack<Integer> b = new Stack<>();
        public void push(int node) {
            a.add(node);
            if (b.isEmpty() || b.peek() >= node) {//如果b棧為空或者b的頂點大於node，則把node加入b棧
                b.add(node);
            }
        }

        public void pop() {
            if (a.pop().equals(b.peek()))//如果a棧退出的值等於b棧頂的值，則棧b也退出棧
                b.pop();
        }

        public int top() {
            return a.peek();//直接返回棧a的棧頂元素
        }

        public int min() {
            return b.peek();//直接返回棧b的棧頂元素
        }
    }

public class MinStack {

        /** initialize your data structure here.
        這個主要是在push的方法中對棧b遇到的x大於棧b以後所進行的變形*/
        Stack<Integer> a, b;
        public MinStack() {
            a = new Stack<>();
            b = new Stack<>();
        }

        public void push(int x) {
            if (b.isEmpty() || b.peek() > x) {
                b.add(x);
            } else {//如果b棧的頂值小於x，則把相同的b.peek()放入b棧
                b.add(b.peek());
            }
            a.add(x);
        }

        public void pop() {
            a.pop();
            b.pop();
        }

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

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