剑指offer:包含min函数的栈(Python)

xiaoxiao2021-02-28  17

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的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()
转载请注明原文地址: https://www.6miu.com/read-2799961.html

最新回复(0)