Question
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.
Example:
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.
Thinking
此題採用Link List實作Stack
My C# Solution
public class MinStack {
private Node top;
private int size = 0;
/** initialize your data structure here. */
public MinStack() {
}
public void Push(int x) {
if (size == 0)
{
top = new Node(x);
top.MinVal = x;
size++;
return;
}
var node = new Node(x);
node.Next = top;
top = node;
top.MinVal = (top.Next.MinVal > x) ? x : top.Next.MinVal;
size++;
}
public void Pop() {
if (size == 0) return;
var node = top;
top = top.Next;
node = null;
size--;
}
public int Top() {
return (size > 0) ? top.Val : 0;
}
public int GetMin() {
return (size > 0) ? top.MinVal : 0;
}
}
public class Node {
public Node Next { set; get; }
public int Val { set; get; }
public int MinVal { set; get; }
public Node(int val)
{
Val = val;
}
}
/**
* 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();
*/
