面试题30. 包含min函数的栈

包含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 次

转载来源：力扣（LeetCode）

---

题目分析

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]
    }

}

代码文件

---