1- 问题描述
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
2- 思路分析
使用两个栈,一个栈保存原始数据(stack),另一个栈保持每个元素对应的最小元素(minStack)。如stack中从栈底到栈顶为[3, 1, 5, 7, 0],那么minStack中从栈底到栈顶为[3, 1, 1, 1, 0]。可参考[LeetCode] Min Stack in Python
3- Python实现
# -*- coding: utf-8 -*-
# Min Stack class MinStack:
def __init__(self):
self.stack = []
self.min = [] # 保存最小值 # @param x, an integer
# @return an integer
def push(self, x): # 入栈
self.stack.append(x)
if not self.min: # 如果min栈为空则直接入栈
self.min.append(x)
return x
if x < self.min[-1]: # 如果入栈元素x比min栈顶小,则x入栈
self.min.append(x)
else: # 如果x比min栈顶大,则重复栈顶元素
self.min.append(self.min[-1])
return x # @return nothing
def pop(self): #出栈
self.stack.pop()
self.min.pop() # min栈同步 # @return an integer
def top(self): #栈顶
return self.stack[-1] # @return an integer
def getMin(self): #栈内最小值
return self.min[-1]