C#LeetCode刷题之#155-最小栈(Min Stack)

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 的时间复杂度应当为 O(n)​ ,其它方法的时间复杂度为: O(1) 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4020

发表评论

登录后才能评论