Min Stack [LeetCode 155]

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实现

 1 # -*- coding: utf-8 -*-
 2 # Min Stack
 3 
 4 class MinStack:
 5     def __init__(self):
 6         self.stack = []
 7         self.min = []    # 保存最小值
 8 
 9     # @param x, an integer
10     # @return an integer
11     def push(self, x):    # 入栈
12         self.stack.append(x)
13         if not self.min: 　　# 如果min栈为空则直接入栈
14             self.min.append(x)
15             return x
16         if x < self.min[-1]:　　# 如果入栈元素x比min栈顶小，则x入栈
17             self.min.append(x)
18         else:　　# 如果x比min栈顶大，则重复栈顶元素
19             self.min.append(self.min[-1])
20         return x
21 
22     # @return nothing
23     def pop(self):    #出栈
24         self.stack.pop()
25         self.min.pop()　　# min栈同步
26 
27     # @return an integer
28     def top(self):    #栈顶
29         return self.stack[-1]
30 
31     # @return an integer
32     def getMin(self):    #栈内最小值
33         return self.min[-1]