美文网首页
LeetCode—— 最小栈

LeetCode—— 最小栈

作者: Minority | 来源:发表于2020-02-11 13:03 被阅读0次

    题目描述

    设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
    
    push(x) -- 将元素 x 推入栈中。
    pop() -- 删除栈顶的元素。
    top() -- 获取栈顶元素。
    getMin() -- 检索栈中的最小元素。
    示例:
    
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.
    
    一、CPP
    1. 双栈法:

    解题思路:投机取巧,使用两个栈,一个栈满足所有的要求。另一个辅助栈用来保存栈的最小值。在计算最小值时,tmp栈顶存放当前最小值,入栈时只判断小于栈顶即可入栈,其他元素(4、5)不用入栈,就算1被pop出后,有2在,他们也算不上是最小值。

    时间复杂度:O(1),“出栈”、“入栈”、“查看栈顶元素”的操作不论数据规模多大,都只是有限个步骤。
    空间复杂度:O(n),n为数据的个数。

    class MinStack {
    public:
        /** initialize your data structure here. */
        stack<int> mystack;
        //tmp用来保存最小值
        stack<int> tmp;
    
        MinStack() {
            
        }
        
        void push(int x) {
            mystack.push(x);
            if(tmp.empty() || tmp.top() >= x){
                tmp.push(x);
            }
        }
        
        void pop() {
            if(mystack.top() == tmp.top()){
                tmp.pop();
            }
            mystack.pop();
        }
        
        int top() {
            return mystack.top();
        }
        
        int getMin() {
            return tmp.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();
     */
    
    • 注意:tmp的入栈条件必须是tmp.top() >= x,而不能是tmp.top() >x。因为tmp.top() >x在测试用例为下时不满足。

    ["MinStack","push","push","push","getMin","pop","getMin"]
    [[],[2],[1],[1],[],[],[]]

    2. 数组双元法:

    解题思路:使用vector来模拟栈,vector中存放的元素为pair类型,pair.first为元素值,pair.second为目前为止,“栈”中的最小元素。维护一个min_val变量来设置每次入栈时的最小值。min_val需要注意的三点就是:

    • 1.当x <= min_val时需要更新最小值
    • 2.当“栈”为空时需要更新最小值
    • 3.当把栈顶元素pop出后,需要更新min_val为次栈顶的pair.second。即把min_val更新为当前最新的最小值。

    时间复杂度:O(1)。有限操作次数。
    空间复杂度:O(n)。

    class MinStack {
    public:
        /** initialize your data structure here. */
        vector< pair<int,int> > vec;
        int min_val = INT_MAX;
    
        MinStack() {
            
        }
        
        void push(int x) {
            if(x <= min_val || vec.size() == 0){
                min_val = x;
            }
            vec.push_back(make_pair(x,min_val));
        }
        
        void pop() {
            vec.pop_back();
            int length = vec.size();
            if(length>0){
                min_val = vec[length-1].second;
            }
        }
        
        int top() {
            int length = vec.size();
            return vec[length-1].first;
        }
        
        int getMin() {
            int length = vec.size();
            return vec[length-1].second;
        }
    };
    
    /**
     * 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();
     */
    
    3. 一栈双元法:(思想同2)
    class MinStack {
    public:
        /** initialize your data structure here. */
        stack< pair<int,int> > mystack;
        int min_val = INT_MAX;
    
        MinStack() {
            
        }
        
        void push(int x) {
            if(x <= min_val || mystack.empty()){
                min_val = x;
            }
            mystack.push(make_pair(x,min_val));
        }
        
        void pop() {
            mystack.pop();
            if(!mystack.empty()){
                min_val = mystack.top().second;
            }
        }
        
        int top() {
            pair<int,int> tmp = mystack.top();
            return mystack.top().first;
        }
        
        int getMin() {
            return mystack.top().second;
        }
    };
    
    /**
     * 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();
     */
    
    二、Java(双栈法)
    public class MinStack {
        private Stack<Integer> s1 = new Stack<>();
        private Stack<Integer> s2 = new Stack<>();
        
        public MinStack() {}  
        public void push(int x) {
            s1.push(x);
            if (s2.isEmpty() || s2.peek() >= x) s2.push(x);
        }
        public void pop() {
            int x = s1.pop();
            if (s2.peek() == x) s2.pop();
        }   
        public int top() {
            return s1.peek();
        }  
        public int getMin() {
            return s2.peek();
        }
    }
    /**
     * 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();
     */
    
    三、Python
    1、双栈法
    class MinStack(object):
        
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.mystack = []
            self.tmp = []
    
        def push(self, x):
            """
            :type x: int
            :rtype: None
            """
            self.mystack.append(x)
            if len(self.tmp) == 0 or self.tmp[-1] >= x:
                self.tmp.append(x)
            
    
        def pop(self):
            """
            :rtype: None
            """
            # pop会返回删除的值
            x = self.mystack.pop()
            if self.tmp[-1] == x:
                self.tmp.pop()
            
    
        def top(self):
            """
            :rtype: int
            """
            return self.mystack[-1]
            
    
        def getMin(self):
            """
            :rtype: int
            """
            return self.tmp[-1]
            
    
    
    # Your MinStack object will be instantiated and called as such:
    # obj = MinStack()
    # obj.push(x)
    # obj.pop()
    # param_3 = obj.top()
    # param_4 = obj.getMin()
    
    2、一栈双元法:
    class MinStack:
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.stack = []
            self.min_val = float("inf")
    
        def push(self, x: int) -> None:
            if self.min_val >= x or len(self.stack) == 0:
                self.min_val = x
    
            self.stack.append((x,self.min_val))  
    
    
        def pop(self) -> None:
            self.tmp = self.stack.pop()
            if len(self.stack):
                self.min_val = self.stack[len(self.stack)-1][1]
    
        def top(self) -> int:
            return self.stack[-1][0]
    
        def getMin(self) -> int:
            return self.stack[-1][1]
            
    
    
    # Your MinStack object will be instantiated and called as such:
    # obj = MinStack()
    # obj.push(x)
    # obj.pop()
    # param_3 = obj.top()
    # param_4 = obj.getMin()
    
    四、各语言及算法时间复杂度

    相关文章

      网友评论

          本文标题:LeetCode—— 最小栈

          本文链接:https://www.haomeiwen.com/subject/potxfhtx.html