【题目】
实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】
- pop、push、getMin操作的时间复杂度都是O(1)
- 设计的栈类型可以使用现成的栈结构
【难度】
士 一星
【解答】
1. 压入数据规则
- 假设当前数据为 newNumber，先将其压入 stackData。然后判断 stackMin 是否为空
- 如果为空，则 newNumber 也压入 stackMin；如果不为空，则比较 newNumber 和 stackMin 的栈顶元素，哪个元素比较小，stackMin 就压入哪个元素
2. 弹出数据规则
- 先判断当前的 stackData 是否为空，再进行弹出
3. 查询最小值操作
- 直接进行查询，返回 stackMin 的栈顶即可
【代码】
class MyStack { private Stack<int> stackData; // 存放着数据 private Stack<int> stackMin; // 作为获取最小值 public MyStack() { stackData = new Stack<int>(); stackMin = new Stack<int>(); } // push: public void push(int number) { stackData.Push(number); if (stackMin.Count == 0) { stackMin.Push(number); } else { if (stackMin.Peek() < number) { stackMin.Push(stackMin.Peek()); } else { stackMin.Push(number); } } } public int pop() { if (stackData.Count == 0) { throw new Exception("Your stack is empty"); } stackMin.Pop(); return stackData.Pop(); } public int getMin() { if (stackMin.Count == 0) { throw new Exception("Your stack is empty"); } return stackMin.Peek(); } }
【点评】
- 时间复杂度O(1) 、空间复杂度O(n)
- 栈和队列的基础题目
