侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

30 包含min函数的栈

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 149 阅读 / 2,565 字 / 正在检测是否收录...

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

解题思路:

可以借助辅助栈,用来保存当前主栈中的最小值,具体如下:

首先有两个栈 $S1$ 和 $S2$,$S1$负责存储压入和弹出所有元素,$S2$ 负责保存当前元素中的最小值。下面通过一个例子来说明,也可以直接看结论。

30-栈的弹出压入

压入阶段

  1. $5$ 压入的时候,$S1$ 正常压入,因为当前 $S2$ 是空的,所以 $5$ 压入 $S2$ 中;
  2. $3$ 压入的时候,$S1$ 正常压入,因为当前 $S2$ 的栈顶元素 $5$ 大于 $3$,所以 $3$ 压入 $S2$;
  3. $4$ 压入的时候,$S1$ 正常压入,因为当前 $S2$ 的栈顶元素 $3$ 小于 $3$,所以 $4$ 不压入 $S2$;
  4. $1$ 压入的时候,$S1$ 正常压入,因为当前 $S2$ 的栈顶元素 $3$ 大于 $1$,所以 $1$ 压入 $S2$;
  5. $2$ 压入的时候,$S1$ 正常压入,因为当前 $S2$ 的栈顶元素 $1$ 小于 $2$,所以 $2$ 不压入 $S2$;

弹出阶段

  1. 当 $2$ 弹出时,$S1$ 正常弹出,因为当前 $S2$ 的栈顶元素 $1$ 不等于 $2$,所以 $S2$ 不弹出;
  2. 当 $1$ 弹出时,$S1$ 正常弹出,因为当前 $S2$ 的栈顶元素 $1$ 等于 $1$,所以 $S2$ 弹出;
  3. 当 $4$ 弹出时,$S1$ 正常弹出,因为当前 $S2$ 的栈顶元素 $3$ 不等于 $4$,所以 $S2$ 不弹出;
  4. 当 $3$ 弹出时,$S1$ 正常弹出,因为当前 $S2$ 的栈顶元素 $3$ 等于 $3$,所以 $S2$ 弹出;
  5. 当 $5$ 弹出时,$S1$ 正常弹出,因为当前 $S2$ 的栈顶元素 $5$ 等于 $5$,所以 $S2$ 弹出;

总结

  • 压入元素 $x$ 时,$S1$ 都是正常压入,而 $S2$ 则需要判断当前的栈顶元素 $a$ 是否大于等于 $x$,如果大于 $x$,说明此时 $a $已经不是最小的了,把 $x$ 压入 $S2$;否则不压入 $S2$。

    • 为什么是大于等于?

      如果连续压入两个最小元素,比如压入两个 $0$,那么 $S2$ 也要压入两次 $0$,这是因为弹出时,是通过判断 $S1$ 和 $S2 $ 栈顶元素是否相等来决定是否要弹出 $S2$ 的。因此在 $a = x$ 的时候,也要将 $x$ 压入 $S2$。

  • 弹出元素 $x$ 时,$S1$ 都是正常弹出,而 $S2$ 则需要判断当前的栈顶元素 $a$ 是否等于 $x$,如果等于,说明 $a$ 是在$x$ 压入时,一起压入 $S2$ 的,需要把 $a$ 弹出。否则不弹出 $S2$ 栈顶元素

代码:

class MinStack {
    /**
     * mainStack 存放着所有的元素
     */
    private final Deque<Integer> mainStack;
    /**
     * minStack 的栈顶存放着 mainStack 中的最小值
     */
    private final Deque<Integer> minStack;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        mainStack = new LinkedList<>();
        minStack = new LinkedList<>();
    }

    public void push(int x) {
        mainStack.push(x);
        if (minStack.isEmpty() || minStack.peek() >= x) {
            minStack.push(x);
        }
    }

    public void pop() {
        // 如果弹出的不是最小值,那么 minStack 就不用动
        // 如果弹出的是最小值,那么 minStack 只需要把栈顶弹出即可
        if (mainStack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return mainStack.isEmpty() ? -1 : mainStack.peek();
    }

    public int min() {
        return minStack.isEmpty() ? -1 : minStack.peek();
    }
}

复杂度分析

  • 时间复杂度$O(1)$push(), pop(), top(), min() 四个函数的时间复杂度均为常数级别。
  • 空间复杂度$O(N)$:当共有 $N$ 个待入栈元素时,辅助栈 $S2$ 最差情况下存储 $N$ 个元素,使用 $O(N)$ 额外空间。
0

评论区