C#LeetCode刷题之#155-最小栈（Min Stack）

问题

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) — 将元素 x 推入栈中。
pop() — 删除栈顶的元素。
top() — 获取栈顶元素。
getMin() — 检索栈中的最小元素。

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin();   –> 返回 -3.

minStack.pop();

minStack.top();      –> 返回 0.

minStack.getMin();   –> 返回 -2.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin();   –> Returns -3.

minStack.pop();

minStack.top();      –> Returns 0.

minStack.getMin();   –> Returns -2.

示例

public class Program {

    public static void Main(string[] args) {
        var minStack = new MinStack();

        minStack.Push(-2);
        minStack.Push(0);
        minStack.Push(-3);

        Console.WriteLine(minStack.GetMin());

        minStack.Pop();

        Console.WriteLine(minStack.Top());
        Console.WriteLine(minStack.GetMin());

        Console.ReadKey();
    }

    public class MinStack {

        private List<int> _list = null;

        private int _minValue = int.MaxValue;

        private void ComputerMinValue() {
            //题目要求，设计一个可以在常数时间内检索到最小元素的栈
            if(_list.Count() != 0) {
                _minValue = _list.Min();
            } else {
                _minValue = int.MaxValue;
            }
        }

        public MinStack() {
            _list = new List<int>();
        }

        public void Push(int x) {
            _list.Add(x);
            ComputerMinValue();
        }

        public void Pop() {
            _list.RemoveAt(_list.Count - 1);
            ComputerMinValue();
        }

        public int Top() {
            return _list[_list.Count - 1];
        }

        public int GetMin() {
            return _minValue;
        }

    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

-3
0
-2

分析：

显而易见，考虑到运行库的使用，Push 和 Pop 的时间复杂度应当为 ​ ，其它方法的时间复杂度为：  。