剑指offer：包含min函数的栈（Python）

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

# -*- coding:utf-8 -*- class Solution: def push(self, node): # write code here def pop(self): # write code here def top(self): # write code here def min(self): # write code here

解题思路

题目要求实现如上四个方法，但是对于Python来说太简单了，没有什么挑战性，看到Java/C们那一长串的代码，用Python的我好心虚。。。 回到这道题，入栈出栈函数比较无脑，需要稍微注意一下min函数。因为实际操作中入栈出栈时动态交替执行，最小值可能被新入栈的更小值替换，也有可能被弹出，导致min值的动态变化。 这里新建一个栈来存储当前的最小值：有更小的值入栈时，将其压入此栈，最小值为栈顶元素；当位于栈顶的最小值出栈后，此时栈顶的元素就顺应称为新的最小值。 我看题目要求实现的top()函数定义什么作用，就偷懒用top()函数返回存储最小值的栈的栈顶元素了。

Python代码

import sys class Solution: def __init__(self): self.list = [] self.minStack = [sys.maxsize] def push(self, node): self.list.append(node) if node < self.top(): self.minStack.append(node) def pop(self): if self.list: popNum = self.list.pop(-1) if popNum == self.top(): self.minStack.pop(-1) return popNum else: return None def top(self): if self.minStack: return self.minStack[-1] else: return None def min(self): return self.top()