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

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