剑指 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();
        }
    }