LeetCode Min Stack

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

class MinStack2 {
private:
    vector<pair<int, int> > mins;
    vector<int> stack;
public:
    void push(int x) {
        stack.push_back(x);
        if (mins.size() == 0) {
            mins.push_back(make_pair(x, 1));
        } else {
            int curr_min = mins.back().first;
            if (curr_min > x) {
                mins.push_back(make_pair(x, 1));
            } else if (curr_min == x) {
                mins.back().second++;
            } else {
                // do nothing
            }
        }
    }

    void pop() {
        if (!stack.size()) {
            return;
        }
        int x = stack.back();
        stack.pop_back();
        if (x == mins.back().first) {
            if (--mins.back().second < 1) {
                mins.pop_back();
            }
        } 
    }

    int top() {
        if (!stack.size()) {
            return 0;
        }
        return stack.back();
    }

    int getMin() {
        if (!stack.size()) {
            return 0;
        }
        return mins.back().first;
    }
};


class MinStack {
private:
    vector<int> mins;
    vector<int> stack;
public:
    void push(int x) {
        stack.push_back(x);
        if (mins.size() == 0) {
            mins.push_back(x);
        } else {
            if (mins.back() >= x) {
                mins.push_back(x);
            }
        }
    }

    void pop() {
        if (!stack.size()) {
            return;
        }
        
        if (stack.back() == mins.back()) {
            mins.pop_back();
        }
        stack.pop_back(); 
    }

    int top() {
        if (!stack.size()) {
            return 0;
        }
        return stack.back();
    }

    int getMin() {
        if (!stack.size()) {
            return 0;
        }
        return mins.back();
    }
};

int main() {
    MinStack stack;
    stack.push(3);
    stack.push(2);
    stack.push(3);

    cout<<stack.getMin()<<endl;
    stack.push(1);
    stack.push(1);
    cout<<stack.getMin()<<endl;
    stack.pop();
    stack.pop();
    cout<<stack.getMin()<<endl;
    return 0;
}

同样的逻辑用java版本的就对，C++就内存超出，难道是vector默认翻倍涨的原因？

第二轮：

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.

没有对连续最小值优化的版本：

// 10:26
class MinStack {
private:
    stack<int> storage;
    stack<int> mins;
public:
    void push(int x) {
        storage.push(x);
        if (mins.empty() || x <= mins.top()) {
            mins.push(x);
        }
    }

    void pop() {
        if (storage.empty()) {
            return;
        }
        int x = storage.top();
        storage.pop();
        if (x <= mins.top()) {
            mins.pop();
        }
    }

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

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