【包含min函数的栈】【2种解法】【剑指offer】

解法 1: 暴力法

直接遍历栈得到最小的元素，但理论上 min 函数的时间复杂度是 O(N)，显然不符合题目要求。

注意：可能由于 js 本身的原因，在牛客网的平台上 ac，这种方法的耗时最少。

解法 2: 辅助栈

正确的做法是借助一个辅助栈。他们之间有一种对应关系：辅助栈的栈顶元素，就是原栈所有元素的最小值。

对原栈和辅助栈的处理过程如下：

  • 元素压入原栈的时候，如果辅助栈为空，或者元素 <= 辅助栈的栈顶元素，那么将元素也压入辅助栈
  • 元素弹出原栈的时候，如果元素等于辅助栈的栈顶元素，辅助栈也弹出元素

这里的判断条件是元素 <= 辅助栈的栈顶元素而不是元素 < 辅助栈的栈顶元素，是为了应对重复元素。例如将 1、2、3、1 依次入栈，采用错误的判断条件，那么辅助栈里面只有 1。在原栈弹出 1 之后，辅助栈为空，就没法获得原栈元素的最小值。

// ac地址：https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
// 原文地址：https://xxoo521.com/2020-01-31-stack-min/

const dataStack = [];
const minStack = [];

function push(value) {
    dataStack.push(value);

    const length = minStack.length;
    if (!length) {
        minStack.push(value);
    } else if (value <= minStack[length - 1]) {
        minStack.push(value);
    }
}

function pop() {
    if (minStack[minStack.length - 1] === dataStack[dataStack.length - 1]) {
        minStack.pop();
    }

    dataStack.pop();
}

function top() {
    return dataStack[length - 1];
}

function min() {
    return minStack[minStack.length - 1];
}

🔍 关注公众号“心谭博客” / 👉 前往 xxoo521.com

查看更多前端与算法的系列文章，获得更好阅读体验