leetcode_155

发表于   |   分类于

Min Stack

题目戳这

题意

就是让你自己实现class来模拟栈的push,pop,top,getMin等操作。

解法

push,pop,top这三个方法都好说，主要是getMin这个方法，楞了一下，如果说每次都找到的话那肯定很费时间，后来发现我们维护一个最小栈minStack就行了。在每次push的时候，我们就比较push的值和minStack的top值，如果push的值比较小，那么我们就把它放到minStack中去，这里我们注意这个条件，并不需要将所有的值都放入这个minStack中去，因为如果不够小的话是不会影响我们getMin得到的结果的，所以那些个值就不用放入minStack中。还有一点就是当pop的时候比较下minStack的top值是否与pop值相等，如果想等的话我们也得把这个值从minStack中pop出去。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class MinStack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minStack = []
    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.stack.append(x)
        if len(self.minStack) == 0 or x<=self.minStack[len(self.minStack)-1]:
            self.minStack.append(x)
        
    def pop(self):
        """
        :rtype: void
        """
        if len(self.stack) >= 0:
            x = self.stack.pop()
            if x == self.minStack[len(self.minStack)-1]:
                self.minStack.pop()
        
    def top(self):
        """
        :rtype: int
        """
        if len(self.stack) >= 0:
            return self.stack[len(self.stack)-1]
        
    def getMin(self):
        """
        :rtype: int
        """
        if len(self.minStack)>0:
            return self.minStack[len(self.minStack)-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()