首页 > 代码库 > 155. Min Stack 求栈的最小值

155. Min Stack 求栈的最小值

2024-11-13 10:50:02   202人阅读

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

  1. class MinStack(object):
  3.     dataList = []
  5.     def __init__(self):
  6.         """
  7.         initialize your data structure here.
  8.         """
  9.         self.dataList = []
  10.         
  12.     def push(self, x):
  13.         """
  14.         :type x: int
  15.         :rtype: void
  16.         """
  17.         curMin = self.getMin()
  18.         if curMin is None or x < curMin:
  19.             curMin = x
  20.         self.dataList.append([x,curMin])
  21.         
  23.     def pop(self):
  24.         """
  25.         :rtype: void
  26.         """
  27.         self.dataList.pop()
  28.         if len(self.dataList) is 0:
  29.             self.curMin = None
  30.         
  32.     def top(self):
  33.         """
  34.         :rtype: int
  35.         """
  36.         if len(self.dataList) is 0:
  37.             return None
  38.         return self.dataList[-1][0]
  39.         
  41.     def getMin(self):
  42.         """
  43.         :rtype: int
  44.         """
  45.         if len(self.dataList) is 0:
  46.             return None
  47.         return self.dataList[-1][1]
  48.         
  51. # Your MinStack object will be instantiated and called as such:
  52. s = MinStack();
  53. s.push(0);
  54. s.push(1);
  55. s.push(0);
  56. s.getMin();
  57. s.pop();
  58. print(s.dataList)
  59. m = s.getMin();
  60. print(m)



来自为知笔记(Wiz)


155. Min Stack 求栈的最小值


联系
我们