-
Difficulty: Easy
-
Related Topics: Stack, Design
Description
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
设计一个栈,支持 push, pop, top 以及取最小元素(全部操作要求在常数时间内完成)
-
push(x) -- Push element x onto stack.
push(x) -- 将元素 x 入栈
-
pop() -- Removes the element on top of the stack.
pop() -- 将栈顶元素出栈
-
top() -- Get the top element
top() -- 获得栈顶元素
-
getMin() -- Retrieve the minimum element in the stack.
getMin() -- 获取栈内的最小元素
Example
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Constraints
-
Methods
pop
,top
, andgetMin
operations will always be called on non-empty stacks.方法
pop
,top
和getMin
总是会在栈非空时调用
Hint
-
Consider each node in the stack having a minimum value. (Credits to @aakarshmadhavan)
考虑栈内的每个节点带上最小元素信息
Solution
数据结构设计题没啥好讲的,根据提示做即可,代码如下:
import kotlin.math.min
class MinStack() {
/** initialize your data structure here. */
/**
* 定义 `pair.first` 为当前元素,`pair.second` 为栈内的最小元素
*/
private val stack = arrayListOf<Pair<Int, Int>>()
fun push(x: Int) {
if (stack.isEmpty()) {
// 栈为空时,直接加入
stack.add(Pair(x, x))
return
}
// 栈非空,把当前最小值拿出来,与要插入的元素比较决定是否更新最小值
val currentMin = stack.last().second
stack.add(Pair(x, min(x, currentMin)))
}
fun pop() {
stack.removeAt(stack.lastIndex)
}
fun top(): Int {
return stack.last().first
}
fun getMin(): Int {
return stack.last().second
}
}
/**
* Your MinStack object will be instantiated and called as such:
* var obj = MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/