题目

实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。

要求

  1. pop、push、getMin 操作的时间复杂度都是 O(1)。
  2. 设计的栈类型可以使用现成的栈结构。

难度

士 ★☆☆☆

解答

在设计时,我们使用两个栈,一个栈用来保存当前栈中的元素,其功能和一个正常的栈没有区别,这个栈记为 stackData;另一个栈用于保存每一步的最小值,这个栈记为 stackMin。具体实现方式有两种。

第一种方案

压入数据规则

假设当前元素为 newNum,先将其压入 stackData,然后判断 stackMin 是否为空。

  • 如果为空,则 newNum 也压入 stackMin。
  • 如果不为空,则比较 newNum 和 stackMin 的栈顶元素中哪一个更小:

    • 如果 newNum <= stackMin,则 newNum 也压入 stackMin;
    • 如果 newNum > stackMin,则 stackMin 不压入任何内容。

举例:依次压入 3、4、5、1、2、1 的过程中,stackData 和 stackMin 的变化如下图所示。

弹出数据规则

先在 stackData 中弹出栈顶元素,记为 value。然后比较当前 stackMin 的栈顶元素和 value 哪一个更小。

通过上文提到的压入规则可知,stackMin 中存在的元素从栈低到栈顶是逐渐变小的,stackMin 栈顶的元素既是 stackMin 栈的最小值,也是当前 stackData 栈的最小值。所以不会出现 value 比 stackMin 的栈顶元素更小的情况,value 只可能大于或等于 stackMin 的栈顶元素。

当 value 等于 stackMin 的栈顶元素时,stackMin 弹出栈顶元素;当 value 大于 stackMin 的栈顶元素时,stackMin 不弹出栈顶元素,返回 value。

很明显可以看出,压入与弹出规则是对应的。

查询当前栈中的最小值操作

由上文的压入数据规则和弹出数据规则可知,stackMin 始终记录着 stackData 中的最小值。所以,stackMin 的栈顶元素始终是当前 stackData 中的最小值。

方案一的代码实现如 MyStack1 类所示:

class MyStack1
{
private:
    stack<int> stackData;
    stack<int> stackMin;
public:
    void push(int newNum)
    {
        if (this->stackMin.empty() || newNum <= this->getMin()) {
            this->stackMin.push(newNum);
        }
        this->stackData.push(newNum);
    }
    
    int pop()
    {
        assert(!this->stackData.empty());
        
        int value = this->stackData.top();
        if (value == this->getMin()) {
            this->stackMin.pop();
        }
        this->stackData.pop();
        return value;
    }
    
    int getMin()
    {
        assert(!this->stackMin.empty());
        
        return this->stackMin.top();
    }
};

第二种方案

压入数据规则

假设当前数据为 newNum,先将其压入 stackData。然后判断 stackMin 是否为空。

如果为空,则 newNum 也压入 stackMin;如果不为空,则比较 newNum 与 stackMin 的栈顶元素中哪一个更小。

如果 newNum 更小或两者相等,则将 newNum 也压入 stackMin;如果 stackMin 的栈顶元素小,则把 stackMin 的栈顶元素重复压入 stackMin。

举例:依次压入 3、4、5、1、2、1 的过程中,stackData 和 stackMin 的变化如下图所示。

弹出数据规则

在 stackData 中弹出数据,弹出的数据记为 value;弹出 stackMin 中的栈顶,返回 value。

很明显可以看出,压入和弹出规则是对应的。

查询当前栈中的最小值操作

由上文的压入数据规则和弹出数据规则可知,stackMin 始终记录着 stackData 中的最小值。所以,stackMin 的栈顶元素始终是当前 stackData 中的最小值。

方案二的代码实现如 MyStack2 类所示:

class MyStack2
{
private:
    stack<int> stackData;
    stack<int> stackMin;
public:
    void push(int newNum)
    {
        if (this->stackMin.empty() || newNum <= this->getMin()) {
            this->stackMin.push(newNum);
        } else {
            int newMin = this->stackMin.top();
            this->stackMin.push(newMin);
        }
        this->stackData.push(newNum);
    }
    
    int pop()
    {
        assert(!this->stackData.empty());
        
        int value = this->stackData.top();
        this->stackMin.pop();
        this->stackData.pop();
        return value;
    }
    
    int getMin()
    {
        assert(!this->stackMin.empty());
        
        return this->stackMin.top();
    }
};

测试

int main(int argc, const char * argv[]) {
    MyStack1 *stack = new MyStack1();
//    MyStack2 *stack = new MyStack2();
    
    int arr[] = {3, 4, 5, 1, 2, 1};
    for (auto num: arr) {
        stack->push(num);
    }
    for (int i = 0; i < 5; i ++) {
        cout << "弹出:" << stack->pop() << " 最小值:" << stack->getMin() << endl;
    }
    return 0;
}

运行结果

弹出:1 最小值:1
弹出:2 最小值:1
弹出:1 最小值:3
弹出:5 最小值:3
弹出:4 最小值:3
Program ended with exit code: 0

总结

方案一和方案二其实都是用 stackMin 栈保存着 stackData 每一步的最小值。共同点是所有操作的时间复杂度都为 O(1)、空间复杂度都为 O(n)。

区别是:方案一中 stackMin 压入时稍省空间,但弹出操作稍费时间;方案二中 stackMin 压入时稍费空间,但弹出操作稍省时间。

Last modification:February 2nd, 2020 at 09:02 pm
如果觉得我的文章对你有用,请随意赞赏