包含min函数的栈
题目描述
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
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 次
题目分析
push、pop、top、size操作时间复杂度为O(1)的栈实现相信大家都非常熟悉,这不是题目的重点;题目着重于实现获取一个栈里最小的元素,获取最小值和最大值的方法大家应该也不陌生,就是在操作的过程中,将当前的最大值或者最小值存放起来,这题也是如此。
由于栈顶的元素可能是当前的minValue,pop之后,minValue的值也要做出相应的改变,这就使得用一个单一的minValue来存放最小值行不通;既然但一个minValue存放行不通,就暴力点,用一个minValue数组存放最小值序列;
维护minValue数组的思想在这里用伪代码解释一下:
fun push(x){
如果 x 比 最小值数组[size] 小
最小值数组[++size] = x
//这样最小值数组前进了一步,原来的第一小数字变成了第二小数字
}
fun pop(){
如果 栈顶元素 等于 最小值数组[size]
size--
//这样最小值数组倒退了一步,原本的第二小数字变成了第一小数字
}
相信到这里大家都知道怎么做了,下面就贴出这道题的题解代码:
class MinStack() {
val normalStack = Array<Int>(20000) {it}
val minStack = Array<Int>(20000) {it}
var normalIndex = 0
var minIndex = 0
fun push(x: Int) {
if(minIndex == 0) {
minStack[minIndex] = x
minIndex++
}else if(x <= minStack[minIndex-1]) {
minStack[minIndex] = x
minIndex++
}
normalStack[normalIndex] = x
normalIndex++
}
fun pop() {
if(normalIndex > 0) {
if (minStack[minIndex - 1] == normalStack[normalIndex - 1])
minIndex--
normalIndex--
}
}
fun top(): Int {
if(normalIndex == 0)
return 0
else
return normalStack[normalIndex-1]
}
fun min(): Int {
if(normalIndex == 0)
return 0
else
return minStack[minIndex-1]
}
}