ACM题解系列之 – 最小堆栈 (Min Stack)

阅读 桌面完整版

没事刷刷题能防止老年痴呆, 而且也能让你随时处于最佳状态, 随时都可以炒老板鱿鱼另谋高就.

题目: 设计一个堆栈(Stack)使 push, pop, 和取最小 min 操作时间复杂度都是 O(1).

这题的难点就是在于怎么样用O(1)常数时间复杂度来取得堆栈里的最小值.

class MinStack {   
public:
    MinStack() {
        // write your code here
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    void push(int number) {
        // write your code here
    }

    /*
     * @return: An integer
     */
    int pop() {
        // write your code here
    }

    /*
     * @return: An integer
     */
    int min() {
        // write your code here
    }
};

例子:

push(1)
pop()   // return 1
push(2)
push(3)
min()   // return 2
push(1)
min()   // return 1

先回顾一下堆栈数据结构. 堆栈是FILO, 也就是先进后出.

在C++里, 我们可以用 STL::vector 来表示堆栈, push 操作对应的就是 push_back 方法, pop 操作对应的是 pop_back 方法, 另外还可以通过 back() 来返回栈最上面的元素(但是并不移除它).

那么, 最方便的办法就是再开一个堆栈用来存储最小值, 每次 push 操作的时候就比较栈最上面的值和即将要插入栈的值哪个小就把它插入到最小栈中. 而 栈弹出的时候也需要对应弹出最小值的栈.

完整的C++方案如下:

class MinStack {
private:
    vector<int> data;
    vector<int> mins;
    
public:
    MinStack() {
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    void push(int number) {
        data.push_back(number);
        if (mins.size() == 0) {
            mins.push_back(number);
        } else {
            int minv = mins.back(); 
            // push updated min value
            mins.push_back(number < minv ? number : minv);
        }
    }

    /*
     * @return: An integer
     */
    int pop() {
        int v = data.back();
        data.pop_back();
        mins.pop_back();
        return v;
    }

    /*
     * @return: An integer
     */
    int min() {
        return mins.back();
    }
};

英文: How to Design a Stack with constant time in Push, Pop, Top, and GetMin ?

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版