LeetCode 面试题 03.02. 栈的最小值-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 面试题 03.02. 栈的最小值。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目

请设计一个栈，除了常规栈支持的 pop 与 push 函数以外，还支持 min 函数，该函数返回栈元素中的最小值。执行 push、pop 和 min 操作的时间复杂度必须为 O(1)。

点击此处跳转题目。

示例：

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

二、C# 题解

要实现 O(1) 复杂度的 min 函数，只需多使用一个数组记录最小值即可：文章来源地址https://www.toymoban.com/news/detail-693930.html

public class MinStack {
    private List<int> data; // 存放栈数据
    private List<int> mins; // 存放对应栈的最小值

    private int p;          // 栈顶指针

    /** initialize your data structure here. */
    public MinStack() {
        data = new List<int>(128);
        mins = new List<int>(128);
        p = -1;
    }
    
    public void Push(int x) {
        data.Add(x);
        if (p == -1) mins.Add(x);
        else mins.Add(x < mins[p] ? x : mins[p]); // 比较 x 与 min，放入更小的一个
        p++;
    }
    
    public void Pop() {
        if (p == -1) return;
        data.RemoveAt(p);
        mins.RemoveAt(p);
        p--;
    }
    
    public int Top() {
        return data[p];
    }
    
    public int GetMin() {
        return mins[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.GetMin();
 */