设计一个支持push、pop、top 操作,并能在常数时间内检索到最小元素的栈.
- push(x) ------ 将元素 x 推入栈中
- pop() ------ 删除栈顶的元素
- top() ------ 获取栈顶的元素
- getMin() ------ 检索栈中的最小元素
摘一个示例做个说明.
示例 1：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
条件分析:
- 栈设计,就是所谓的压入栈,弹出栈操作
- 最小元素获取 -> 需要快速获取最小值
解决思路1:
- 根据分析1,采用数据结构数组进行操作
- 设计最小值
利用数组的特性进行压入、弹出操作,设计最小值属性,直接返回
class MinStack {
/// 栈数据存储
var data: [Int] = []
/// 最小值
var minNum: Int?
init() {
}
func push(_ val: Int) {
/// 入栈,数组加操作,然后对比最小值
self.data.append(val)
minNum = min(minNum ?? .max, val)
}
func pop() {
/// 出栈
let last = self.data.popLast()
/// 最小值判断
if last == minNum {
minNum = self.data.min()
}
}
func top() -> Int {
return self.data.last!
}
func getMin() -> Int {
return minNum!
}
}
最小栈提交结果.jpg
测试用例:
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
考察要点:
- 栈
- 设计
