题目描述
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
1 2 3 4 5 6 7 8
| MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.
|
提示:
- 各函数的调用总次数不超过 20000 次
解题思路
方法一:辅助栈
方法二:头插法链表
方法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class MinStack { Node head;
public MinStack() { } public void push(int x) { if (head == null) { head = new Node(null, x, x); } else { head = new Node(head, x, Math.min(head.min, x)); } } public void pop() { head = head.next; } public int top() { return head.val; } public int min() { return head.min; } }
class Node { Node next; int val; int min;
public Node(Node next, int val, int min) { this.next = next; this.val = val; this.min = min; } }
|