题目描述

blablabla

每次push(x)都用lower_bound(v.begin(), v.end(), x)查找x的位置插入, 类似插入排序
pop()时也删除对应vector里栈顶元素的值就好啦
很low的一种做法 T_T

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class MinStack {
public:
    /** initialize your data structure here. */
    vector<int> v; //有序的数组
    stack<int> stk;

    MinStack() {

    }

    void push(int x) {
        vector<int>::iterator it = lower_bound(v.begin(), v.end(), x);
        v.insert(it, x); //把x插入合适的位置
        stk.push(x);
    }

    void pop() {
        int t = stk.top();
        vector<int>::iterator it = lower_bound(v.begin(), v.end(), t); //从有序的vector里找出栈顶元素的位置 删掉
        stk.pop();
        v.erase(it);
    }

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

    int getMin() {
        return v[0];
    }
};

/**
 * 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.getMin();
 */

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla