[每日一题] 第二十七题:包含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.

提示:

  1. 各函数的调用总次数不超过 20000 次

题解

方法一:辅助栈

解题思路

普通栈的 push()pop() 函数的复杂度为 O(1),而获取栈最小值 min() 函数需要遍历整个栈,复杂度为 O(N)。

  • 本题难点:将 min() 函数复杂度降为 O(1),可通过建立辅助栈实现;

    • 数据栈 A:栈 A 用于存储所有元素,保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑;
    • 辅助栈 B:栈 B 中存储栈 A 中所有 非严格降序 的元素,则栈 A 中的最小元素始终对应栈 B 的栈顶元素,即 min() 函数只需返回栈 B 的栈顶元素即可。
  • 因此,只需设法维护好栈 B 的元素,使其保持非严格降序,即可实现 min() 函数的 O(1) 复杂度。

[每日一题] 第二十七题:包含min函数的栈

函数设计

  • push(x) 函数:重点为保持栈 B 的元素是 非严格降序 的。

    1. 将 x 压入栈 A(即 A.add(x));
    2. 若 ① 栈 B 为空 或 ② x 小于等于 栈 B 的栈顶元素,则将 x 压入栈 B(即 B.add(x))。
  • pop() 函数:重点为保持栈 A B 的 元素一致性

    1. 执行栈 A 出栈(即 A.pop()),将出栈元素记为 y;
    2. 若 y 等于栈 B 的栈顶元素,则执行栈 B 出栈(即 B.pop())。
  • top() 函数:直接返回栈 A 的栈顶元素即可,即返回 A.peek()

  • min() 函数:直接返回栈 B 的栈顶元素即可,即返回 B.peek()

代码

Java 代码中,由于 Stack 中存储的是 int 的包装类 Integer,因此需要使用 equals() 代替 == 来比较值是否相等。

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

复杂度分析

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

个人理解

  1. 比较两个值相等一定要用 equals() 方法,因为 Stack 中存的是 Integer,不能用 == 来判断相等。
  2. 元素一致性:上面代码中已经有了处理元素一致性的方法,就是在 A 栈中 pop 出来的元素,如果和 B 栈的栈顶元素相等,则将 B 栈的栈顶元素也 pop 出来。我们来看一下为什么这么做可以保证元素一致性。
    1. B 栈是非严格递减的,也就是说,在向 A 栈内添加元素的时候,如果后面的一个元素大于前面一个元素,是不会将元素压入 B 栈中的。
    2. 这就避免了我在 A 栈中弹出一个元素,结果在 B 栈中存在,但是不在栈顶,导致最后 B 栈元素不空等各种问题。因为我根本不会将大值压入 B 栈中。所以只需要比较栈顶元素即可,非严格递减存储的。
    3. 为什么这样可以,假设压入 A 栈中第一个元素是最小的,那么 B 栈只会有一个元素,整个过程中最小元素都是第一个,直到 A 中 pop 出最后一个元素。

方法二:我的解法

我是借鉴了上面的解法,不过我使用的是 Deque,因为 Stack 已经不推荐使用了。

class MinStack {

    Deque<Integer> A,B;

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

    public void push(int x) {
        A.addFirst(x);
        if (B.isEmpty() ||  x <= B.peekFirst()) {
            B.addFirst(x);
        }
    }

    public void pop() {
        if (A.removeFirst().equals(B.peekFirst())) {
            B.removeFirst();
        }
    }

    public int top() {
        return A.peekFirst();
    }

    public int min() {
        return B.peekFirst();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

题解来源

作者:jyd
链接:leetcode-cn.com/problems/bao-han-m...
来源:力扣(LeetCode)

题目来源

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/bao-han-m...

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!