LeetCode 155 Min Stack（最小棧）

LeetCode 155 Min Stack（最小棧）

翻譯

設計支持push、pop、top和在常量時間內檢索最小元素的棧。

push(x) —— 推送元素X進棧
pop() —— 移除棧頂元素
top() —— 得到棧頂元素
getMin() —— 檢索棧的最小元素

原文

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

分析

之前寫過兩道題，分別是用Stack來實現Queue的功能以及用Queue來實現Stack的功能，這裡如果也使用兩個Stack的話就非常容易了。

LeetCode 225 Implement Stack using Queues（用隊列來實現棧）（*）

LeetCode 232 Implement Queue using Stacks（用棧來實現隊列）（*）

class MinStack {
public:
    stack allStack;
    stack minSta;

    void push(int x) {
        if (allStack.empty()) {
            allStack.push(x);
            minSta.push(x);
        }
        else {
            allStack.push(x);
            if (x <= minSta.top()) minSta.push(x);
        }
    }

    void pop() {
        if (allStack.top() == minSta.top()) {
            minSta.pop();
        }
        allStack.pop();
    }

    int top() {
        return allStack.top();
    }

    int getMin() {
        return minSta.top();
    }                                  
};

除了上面的stack，我還用vector實現了：

class MinStack {
public:
    vector allVec;
    vector minVec;

    void push(int x) {
        if (allVec.empty()) {       
            allVec.push_back(x);
            minVec.push_back(x);
        }
        else {
            if (x <= minVec[minVec.size() - 1]) {
                minVec.push_back(x);
            }
            allVec.push_back(x);
        }
    }

    void pop() {
        if (allVec[allVec.size() - 1] == minVec[minVec.size() - 1])
            minVec.erase(minVec.end() - 1);
        allVec.erase(allVec.end() - 1);
    }

    int top() {
        return allVec[allVec.size() - 1];
    }

    int getMin() {
        return minVec[minVec.size() - 1];
    }
};

然而用vector效率反而更低了……