LeetCode-面试题30-包含min函数的栈

benym

发布于 2022-07-14 15:10:03

1200

发布于 2022-07-14 15:10:03

文章被收录于专栏：后端知识体系

# LeetCode-面试题30-包含min函数的栈

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

示例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 次

# 解题思路

辅助栈：数据栈再压入元素的时候与辅助栈的顶层元素(即之前数据栈的最小元素)做比较，如果比它小，就把值x同时压入数据栈和辅助栈。如果比它大，说明此时最小元素仍然是之前的最小元素，把辅助栈的栈顶取出来，数据栈压入x，辅助栈压入原本的辅助栈栈顶元素。这样就能保证辅助栈始终存放当前数据栈的最小值，在弹出数据时，同时弹出数据栈和辅助栈栈顶

# Java代码

class MinStack {
    private Stack<Integer> stack_data;
    private Stack<Integer> stack_min;
    /** initialize your data structure here. */
    public MinStack() {
        stack_data = new Stack<>();
        stack_min = new Stack<>();
    }
    
    public void push(int x) {
        stack_data.push(x);
        if(stack_min.size()==0||x<stack_min.peek())
            stack_min.push(x);
        else
            stack_min.push(stack_min.peek());
    }
    
    public void pop() {
        stack_data.pop();
        stack_min.pop();
    }
    
    public int top() {
        return stack_data.peek();
    }
    
    public int min() {
        return stack_min.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.min();
 */

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除

java