c/c++ leetcode 155.最小栈

题目描述:

难度简单634

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。

pop() —— 删除栈顶的元素。

top() —— 获取栈顶元素。

getMin() —— 检索栈中的最小元素。

解法一:双栈

class MinStack {    stack
   
     s;    stack
    
      minStack;    int t;public:    /** initialize your data structure here. */    MinStack() {        //先在最小栈里存放int 类型的最大数值//如果不存,也是可以的,需要加一个minStack.empty()的判断        //如果为空x就不需要与minStack判断        minStack.push(INT_MAX);    }        void push(int x) {        s.push(x);        //如果最小栈的栈顶元素小于x 就再次把最小栈的栈顶元素进栈 否则就把x 进栈        minStack.push(min(minStack.top(),x));    }        void pop() {        s.pop();        minStack.pop();    }        int top() {        return s.top();    }        int getMin() {       return minStack.top();    }};/** * 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(); */

另一个版本

国外友人的杰作链接:https://leetcode.com/problems/min-stack/discuss/49016/C%2B%2B-using-two-stacks-quite-short-and-easy-to-understand

class MinStack {private:    stack
   
     s1;    stack
    
      s2;public:    void push(int x) {	    s1.push(x);	    if (s2.empty() || x <= getMin())  s2.push(x);	        }    void pop() {        //在这里判断一下就是s2最小栈 二个栈中栈顶元素相同最小栈中的元素才会出栈;	    if (s1.top() == getMin())  s2.pop();	    s1.pop();    }    int top() {	    return s1.top();    }    int getMin() {	    return s2.top();    }};

时空复杂度分析:

时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，插入和删除也都是常数级别的时间复杂度;

空间复杂度 :N 为进栈的最多的个数。最坏情况下，光进栈不出栈，此时两个栈占用的空间为 O(2n)去掉常数也就是O(N);

解法二.用一个栈来存储一个键值对

这也是一个国外友人的一个杰作链接:https://leetcode.com/problems/min-stack/discuss/49221/C%2B%2B-solution-using-pair-and-one-stack

也是一个对于STL熟悉的老手了

class MinStack {     stack
   
    
     > st;public:    void push(int x) {        int min;        if (st.empty()) {            min = x;        }        else {            min = std::min(st.top().second,x);        }        st.push({x, min});    }    void pop() {        st.pop();    }    int top() {        return st.top().first;    }    int getMin() {        return st.top().second;    }};

时间复杂度都一样

转载地址：http://udyki.baihongyu.com/

你可能感兴趣的文章