Initial Solution
class MinStack:
minVal = 0
def __init__(self):
self.stack = []
self.minSortedStack= []
def push(self, val: int) -> None:
self.stack.append(val)
self.minVal = min(self.minVal, val)
tmpStack = []
while len(self.minSortedStack) > 0 and self.minSortedStack[-1] < val:
tmpStack.append(self.minSortedStack[-1])
self.minSortedStack.pop()
self.minSortedStack.append(val)
self.minSortedStack += tmpStack[::-1]
def pop(self) -> None:
topVal = self.top()
self.stack.pop()
tmpStack = []
while len(self.minSortedStack) > 0 and self.minSortedStack[-1] != topVal:
tmpStack.append(self.minSortedStack[-1])
self.minSortedStack.pop()
self.minSortedStack.pop() # topVal
self.minSortedStack += tmpStack[::-1]
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minSortedStack[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n) for push and pop operations due to maintaining the sorted stack, O(1) for top and getMin operations.
Space Complexity: O(n) for storing both the main stack and the minimum sorted stack.
Other Better Solutions
class MinStack:
def __init__(self):
self.stack = [] # 값들
self.mins = [] # 현재까지의 최소값들
def push(self, val: int) -> None:
self.stack.append(val)
if not self.mins:
self.mins.append(val)
else:
self.mins.append(min(val, self.mins[-1]))
def pop(self) -> None:
self.stack.pop()
self.mins.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.mins[-1]
Python
복사
Time complexity and Space Complexity
Time Complexity: O(1) for all operations (push, pop, top, getMin).
Space Complexity: O(n) for storing both the main stack and the mins stack, where each element tracks the minimum value up to that point.