Magic power of 'is not None'


  • 3
    G

    This code doesn't work until I delete is not None

    def push(self, x):
    	self.stk.append(x)
    	if self.mini is not None: # Memory Limit Exceeded with this
    		if x < self.mini:
    		    self.mini = x
    	else:
    		self.mini = x
    	return x
    

    And this one works

    def push(self, x):
    	self.stk.append(x)
    	if self.mini:
    		if x < self.mini:
    		    self.mini = x
    	else:
    		self.mini = x
    	return x
    

    why??



    Accepted code

    class MinStack:
        # @param x, an integer
        
        def __init__(self):
        	self.mini = None
        	self.stk = []
    
        def push(self, x):
        	self.stk.append(x)
        	if self.mini:
        		if x < self.mini:
        		    self.mini = x
        	else:
        		self.mini = x
        	return x
    	
        # @return nothing
        def pop(self):
        	top = self.stk.pop()
        	if top == self.mini:
        		if self.stk:
        			self.mini = min(self.stk)
        		else:
        			self.mini = None
        	return top
    
        # @return an integer
        def top(self):
        	return self.stk[-1]
    
        # @return an integer
        def getMin(self):
        	return self.mini

  • 0
    S

    not sure why MLE, but your pop takes O(n) in worst case.


  • 0
    I

    i think is not None is on the right way(although it can not AC).
    what will we get when the minstack object push 0 first, then push 1, then push 2 for the AC code?
    we will get the wrong result from the getMin method.

    mystk = MinStack()
    print mystk.getMin()
    mystk.push(0)
    print mystk.getMin()
    mystk.push(1)
    print mystk.getMin()
    mystk.push(2)
    print mystk.getMin()


  • 0
    G

    You are right. 0 should be different with None, and this can be solved by change the if...else order and use if self.mini is None.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.