0155. 最小栈

0155. 最小栈 #

  • 标签:栈、设计
  • 难度:简单

题目大意 #

要求:设计一个「栈」。实现 pushpoptopgetMin 操作,其中 getMin 要求能在常数时间内实现。

解题思路 #

题目要求在常数时间内获取最小值,所以我们不能在 getMin 操作时,再去计算栈中的最小值。而是应该在 pushpop 操作时就已经计算好了最小值。

我们有两种思路来解决这道题。

思路一:使用辅助栈保存当前栈中的最小值。在元素入栈出栈时,两个栈同步保持插入和删除。具体做法如下:

  • push 操作:当一个元素入栈时,取辅助栈的栈顶存储的最小值,与当前元素进行比较得出最小值,将最小值插入到辅助栈中;该元素也插入到正常栈中。
  • pop 操作:当一个元素要出栈时,将辅助栈的栈顶元素一起弹出。
  • top 操作:返回正常栈的栈顶元素值。
  • getMin 操作:返回辅助栈的栈顶元素值。

思路二:使用一个栈,保存元组:(当前元素值,当前栈内最小值)。具体操作如下:

  • push 操作:如果栈不为空,则判断当前元素值与栈顶元素所保存的最小值,并更新当前最小值,然后将新元素和当前最小值组成的元组保存到栈中。
  • pop操作:正常出栈,即将栈顶元素弹出。
  • top 操作:返回栈顶元素保存的值。
  • getMin 操作:返回栈顶元素保存的最小值。

代码 #

  • 思路一:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MinStack:

    def __init__(self):
        self.stack = []
        self.minstack = []

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(val)
            self.minstack.append(val)
        else:
            self.stack.append(val)
            self.minstack.append(min(val, self.minstack[-1]))
        
    def pop(self) -> None:
        self.stack.pop()
        self.minstack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minstack[-1]
  • 思路二:
 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
class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    class Node:
        def __init__(self, x):
            self.val = x
            self.min = x

    def push(self, val: int) -> None:
        node = self.Node(val)
        if len(self.stack) == 0:
            self.stack.append(node)
        else:
            topNode = self.stack[-1]
            if node.min > topNode.min:
                node.min = topNode.min

            self.stack.append(node)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1].val

    def getMin(self) -> int:
        return self.stack[-1].min
本站总访问量  次  |  您是本站第  位访问者