
问题
设计一个支持 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 的时间复杂度应当为 ,其它方法的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4020。