题目描述
设计一个支持 push，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 输入：
["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.
|
提示：
-231 <= val <= 231 - 1- ``pop
、top和getMin` 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
题解
思路：
一个栈用来存当前栈上的数据，借助另一个栈来记录每次push或pop后栈上的最小值。
可以用数组的头元素做栈顶，也可以用数组的尾元素做栈顶。
使用数组的末尾元素更节省开销。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class MinStack {
var values = [Int]()
var minValues = [Int.max]
init() {}
func push(_ val: Int) {
values.append(val)
minValues.append(min(val, minValues[minValues.count - 1]))
}
func pop() {
values.removeLast()
minValues.removeLast()
}
func top() -> Int {
return values[values.count - 1]
}
func getMin() -> Int {
return minValues[minValues.count - 1]
}
}
|