剑指Offer系列_30_包含min函数的栈

以空间换时间：
package leetcode.sword_to_offfer.day01;

import java.util.Stack;

/**

 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

 * <p>

 * 示例:

 * <p>

 * MinStack minStack = new MinStack();

 * minStack.push(-2);

 * minStack.push(0);

 * minStack.push(-3);

 * minStack.min();   --> 返回 -3.

 * minStack.pop();

 * minStack.top();      --> 返回 0.

 * minStack.min();   --> 返回 -2.

 * <p>

 * <p>

 * 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.min();

 *

 * @author soberw

 * @Classname MinStack

 * @Description

 * @Date 2022-02-07 9:16

 */

public class MinStack {

    private final Stack<Integer> st;

    private int minValue = Integer.MAX_VALUE;  //存放最小值

    /**

     * initialize your data structure here.

     */

    public MinStack() {

        st = new Stack<>();

    }

    public void push(int x) {

        st.push(minValue);  //存入当前最小值

        minValue = Math.min(x, minValue);  //保证当前minValue最小

        st.push(x); // 存入数据

    }

    public void pop() {

        st.pop();  //出栈

        minValue = st.pop(); //存放的最小值出栈

    }

    public int top() {

        return st.peek();

    }

    public int min() {

        return minValue;

    }

}
简单示意图：
巴特西

剑指Offer系列_30_包含min函数的栈

最新文章

热门文章
