LeetCode -- Min Stack

LeetCode -- Min Stack

題目描述：


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.


設計一個棧，要求獲取最小值的時間復雜度為常數。


思路：
對變成語言類庫內部的棧進行封裝，維護使用一個最小值的成員即可。要注意的就是彈出棧的操作，如果棧中依然有值，需要求出當前最小值更新最小值；如果棧空，最小值設為空。


實現代碼：

public class MinStack {
    private Stack _stack ;
	private int? _min;
	public MinStack(){
		_stack = new Stack();
	}
    public void Push(int x) {
        if(!_min.HasValue || x < _min){
			_min = x;
		}
		_stack.Push(x);
    }


    public void Pop() {
        var x = _stack.Pop();
		if (x == _min){
			if(_stack.Count > 0){
				_min = _stack.Min();
			}
			else{
				_min = null;
			}
		}
    }


    public int Top() {
        return _stack.Peek();
    }


    public int GetMin() {
        return _min.Value;
    }
}