Python教程

剑指 Offer 30. 包含min函数的栈(python3编写)

本文主要是介绍剑指 Offer 30. 包含min函数的栈(python3编写),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

  • 1、题目描述:
  • 2、方法:
    • 思路:
    • 代码:

1、题目描述:

在这里插入图片描述

2、方法:

思路:

思路来源:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/

普通栈的 p u s h ( ) push() push() 和 p o p ( ) pop() pop() 函数的复杂度为 O ( 1 ) O(1) O(1) ,而获取栈最小值 m i n ( ) min() min() 函数需要遍历整个栈,复杂度为 O ( N ) O(N) O(N)。

本题难点在于: 将 min() 函数复杂度降为 O ( 1 ) O(1) O(1) ,可通过建立辅助栈实现。细节下面一一说来:

数据栈 A A A : 栈 A A A 用于存储所有元素,保证入栈 p u s h ( ) push() push() 函数、出栈 p o p ( ) pop() pop() 函数、获取栈顶 t o p ( ) top() top() 函数的正常逻辑。
辅助栈 B B B : 栈 B B B 中存储栈 A A A 中所有 非严格降序 的元素,则栈 A A A 中的最小元素始终对应栈 B B B 的栈顶元素,即 m i n ( ) min() min() 函数只需返回栈 B B B 的栈顶元素即可。

因此,只需设法维护好 栈 B B B 的元素,使其保持非严格降序,即可实现 m i n ( ) min() min() 函数的 O ( 1 ) O(1) O(1) 复杂度。如下图所示:
在这里插入图片描述

如果还有点懵逼,下面我说一下具体的做法就知道怎么回事了:

  • 当元素入栈时,即执行 p u s h ( ) push() push()函数时,我们将元素压入数据栈 A A A中,同时检查当前辅助栈 B B B的情况:辅助栈 B B B为空或者当前要 p u s h ( ) push() push()的元素小于等于辅助栈 B B B栈顶的元素,则把当前元素也压入辅助栈 B B B。
  • 当元素出栈时,我们把数据栈 A A A栈顶的元素弹出,同时检查数据栈 A A A栈顶元素是不是等于辅助栈 B B B栈顶元素,如果等于,则把辅助栈 B B B栈顶元素也出栈。

代码:

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stackA = [] # 数据栈
        self.stackB = [] # 辅助栈


    def push(self, x: int) -> None:
        self.stackA.append(x)
        if not self.stackB or self.stackB[-1] >= x:
            self.stackB.append(x) # 如果stackB为空,或者x小于等于栈顶元素,则x直接入stackB


    def pop(self) -> None:
        # 栈B中存储栈A中所有非严格降序的元素,则栈A中的最小元素始终对应栈B的栈顶元素
        if self.stackA.pop() == self.stackB[-1]:
            self.stackB.pop()


    def top(self) -> int:
        return self.stackA[-1] # 栈顶元素


    def min(self) -> int:
        return self.stackB[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()
这篇关于剑指 Offer 30. 包含min函数的栈(python3编写)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!