Smarter Python数据结构：根据入栈序列来判断可能的出栈序列&&利用O(1)的时间复杂度求栈中最小元素

欢迎关注微信公众号：简说Python
关注后回复：1024，可以领取精选编程学习电子书籍。

这两天和几个朋友组了个互相督促学习群，想着督促一下自己学习，也督促自己的原创输出，其实很多时候都是懒，真不是没有东西可以写了，这不，我在我的免费知识星球简说编程里开了个新的标签日常编程问题，后面我会把自己学习工作中遇到的一些问题和解决方法记录到里面，有些可以扩展的点，我会写到微信公众号里。
我定的目标是：

我简单写了个规则，大家说可以，然后，我们就开始吧，我习惯把该做的事情提前一天做（如果有时间的话）。

今天给大家分享的书籍《Python程序员面试算法宝典》第二章第四和第五小节：根据入栈序列来判断可能的出栈序列和利用O(1)的时间复杂度求栈中最小元素。

如果你是第一次看，也许，你可以看看本系列下面的文章：
Python数据结构：链表合集（12+7），复现几遍，包你学会
Smaller Python数据结构：自己动手实现栈
Smaller Python数据结构：自己动手实现队列
Smarter Python数据结构：如何翻转栈

今日问题1:根据入栈序列来判断可能的出栈序列

"""
目标：写一个程序，根据入栈序列判断给定的序列是不是出栈序列

输入：push"1, 2, 3, 4, 5"  pop"3, 2, 5, 4, 1"
输出：True


Goal: write a program to determine whether a given
 sequence is a stack out sequence according to the 
 stack in sequence
 
Input: push "1, 2, 3, 4, 5" pop "3, 2, 5, 4, 1"
Output: True
"""

解题

首先我们之前已经写好了栈的基本操作，在b_1_implementation_stack.py文件中，所以我们先导入这两个包。

from StackQueueHash.b_1_implementation_stack import LinkStack

方法一：遍历pop push比较

"""
Method One : 遍历pop,push比较

核心思想：先遍历push序列进行push，同时判断栈是否为空，而且栈顶元素是否等于
pop序列当前元素，如果栈不为空而且栈顶元素等于pop序列当前元素，则说明按pop
序列，当前元素应该出栈，执行出栈操作，然后继续遍历，到遍历结束，如果栈为空，
而且pop序列遍历指针指到序列尾，则说明，pop序列是栈的一个出栈序列，否则，不是。

时间复杂度：O(N)
空间复杂度：O(N)  需要构建一个栈

Method One:

Core idea: first traverse the push sequence to push, and at the same
 time judge whether the stack is empty, and whether the top element 
 of the stack is equal to the current element of the pop sequence. 
 If the stack is not empty and the top element of the stack is equal 
 to the current element of the pop sequence, it means that according to 
 the pop sequence, the current element should be out of the stack, perform 
 the stack operation, and then continue to traverse until the end of the 
 traverse. If the stack is empty, and the pop sequence traverse The pointer 
 to the end of the sequence indicates that the pop sequence is a stack out 
 sequence, otherwise, it is not.
 
Time complexity: O (n)
Spatial complexity: O (n)  needs to build a stack
"""

代码

def judge_pop_from_push(s1, s2):
    if not s1 or not s2:
        return False
    len_push = len(s1)
    len_pop = len(s2)
    if len_pop != len_push:
        return False
    s = LinkStack()  # 初始化一个栈对象
    index_pop = 0
    for i in range(len_push):   # 遍历push序列
        s.stack_push(s1[i])  # 入栈
        while not s.stack_is_empty() and s.get_stack_top() == s2[index_pop]:
            # 栈不为空，而且栈顶元素与pop序列相等
            s.stack_pop()  # 出栈
            index_pop += 1  # pop序列后移
    # 栈为空，pop序列遍历到尾，说明pop序列是push序列的出栈序列，一个入栈对应一个出栈
    return s.stack_is_empty() and index_pop == len_pop

参考思路

测试代码

# 当然，也许还有别的方法，比如建一个辅助的链表
# 欢迎你说出你的想法


# 程序入口，测试函数功能
if __name__ == "__main__":
    s1 = "12345"
    s2 = "53412"
    result = judge_pop_from_push(s1, s2)
    if result:
        print("序列'%s'是序列'%s'的一种出栈序列。" % (s2, s1))
    else:
        print("序列'%s'不是序列'%s'的一种出栈序列。" % (s2, s1))

运行结果

今日问题2:利用O(1)的时间复杂度求栈中最小元素

"""
目标：写一个程序，用O(1)的时间复杂度求栈中最小元素

输入：1，4，5，2，6
输出：当前最小元素为：1


Goal: write a program to find the minimum elements
 in the stack with O (1) time complexity.
Input: 1, 4, 5, 2, 6
Output: the current minimum element is: 1
"""

解题

首先我们之前已经写好了栈的基本操作，在b_1_implementation_stack.py文件中，所以我们先导入这两个包。

from StackQueueHash.b_1_implementation_stack import LinkStack

方法一：借助辅存

"""
Method One : 借助辅存

核心思想：新建一个栈（min_stack），存储栈的最小值每次主栈进行push时，把push
的元素与min_stack栈顶元素比较大小，如果比min_stack栈顶元素小，则同时将该元素
push到min_stack，否则不操作min_stack；主栈进行pop操作时，同时把pop出的元素
与min_stack栈顶比较，如果相等，着min_stack也执行pop操作，否则min_stack不操作。

每次要取栈最小元素，直接取min_stack栈顶即可。

时间复杂度：O(1)
空间复杂度：O(N)

Method one: with the help of auxiliary storage

Core idea: Create a new stack (min_stack), store the minimum value of
 the stack, and each time the main stack pushs, the push element is 
 compared to the min_stack stack top element, and if it is smaller 
 than the min_stack stack top element, the element is pushed to the 
 min_stack. Otherwise, the min_stack is not operated; when the main 
 stack is pooped, the pop-out element is compared to the top of the 
 min_stack stack, and if equal, the min_stack also performs the pop 
 operation, otherwise the min_stack does not operate.
 
Each time you want to take the smallest element of the stack, you
 can take the top of the stack directly min_stack.
 
Time complexity: O (1)
Spatial complexity: O (n)
"""

代码

class MyStack1:
    def __init__(self):
        self.my_stack = LinkStack()  # 主栈，存储数据
        self.min_stack = LinkStack()  # 辅助栈，存储最小元素

    # 写一个类，专门处理进栈和出栈情况
    def push(self, x):  # 入栈
        # 先将数据入主栈
        self.my_stack.stack_push(x)
        # 与辅存内的最小元素比较
        if self.min_stack.stack_is_empty() or x < self.min_stack.get_stack_top():
            self.min_stack.stack_push(x)  # 如果辅助栈为空或者当前push的数比辅助栈顶元素小，则入栈

    def pop(self):  # 出栈
        # 先将数据从主栈中取出
        top = self.my_stack.get_stack_top()
        # 出栈
        self.my_stack.stack_pop()
        # 与辅存内最小元素比较
        if top == self.min_stack.get_stack_top():
            self.min_stack.stack_pop()  # 如果出栈的元素就是最小元素，则min_stack也要出栈，最小值改变

    def get_min(self):  # 获取最小元素
        if self.min_stack.stack_is_empty():  # 栈内还没有元素
            return None
        return self.min_stack.get_stack_top()  # 返回min_stack栈顶

    def get_top(self):  # 获取栈顶元素
        return self.my_stack.get_stack_top()

方法二：数组（列表）实现栈

"""
Method Two : 另辟蹊径法
思路参考：https://mp.weixin.qq.com/s/thGupqL1TvNe8c8ztDAfvw

核心思想：在栈内存储的是当前最小值和push进了的元素的差值，这样我只需要新建
一个变量来存储最小值即可。其中比较复杂的是对入栈，出栈的处理，还有如何获取栈
顶真实值，其实根据运算规则即可得出，详细见代码。

时间复杂度：O(1)
空间复杂度：O(1)

Method two: another way

Core idea: the difference between the current minimum value and the
 pushed element is stored in the stack, so I only need to create a 
 new variable to store the minimum value. Among them, the more 
 complex is the processing of stack in and stack out, as well as how 
 to obtain the real value of the top of the stack. In fact, it can be 
 obtained according to the operation rules. See the code for details.

Time complexity: O (1)
Space complexity: O (1)
"""

代码

class MyStack2:
    def __init__(self):
        self.min_element = None   # 存储最小值
        self.my_stack = LinkStack()  # 主栈，存储数据

    # 写一个类，专门处理进栈和出栈情况
    def push(self, x):  # 入栈
        if self.my_stack.stack_is_empty():  # 第一次入栈
            self.min_element = x  # 第一个入栈元素直接为最小值
            self.my_stack.stack_push(0)  # 差值为0
        else:
            sub = x - self.min_element  # 做差
            # 将差值push进主栈
            self.my_stack.stack_push(sub)
            # 如果sub小于0，说明新入栈元素更小
            if sub < 0:
                self.min_element = x  # 替换最小值

    def pop(self):  # 出栈
        if not self.my_stack.stack_is_empty():  # 栈不为空，才可以出栈
            top = self.my_stack.get_stack_top()  # 获取栈顶元素
            if top < 0:  # 如果栈顶元素小于0，说明该元素为栈内最小值
                self.min_element = self.min_element - top  # 最小值出栈后，现在最小值变成原来第二小的值
            self.my_stack.stack_pop()  # 出栈

    def get_min(self):  # 获取最小元素
        return self.min_element  # 直接返回最小元素

    # 获取栈顶元素
    def get_top(self):
        if self.my_stack.get_stack_top() < 0:  # 如果栈顶元素小于0，说明当前栈顶为最小元素
            self.min_element = self.min_element - self.my_stack.get_stack_top()  # 为了找到真实值，需要先找到上一个min_element
            x = self.min_element + self.my_stack.get_stack_top()
            # 实际栈顶元素 = 最小值 - 差值（当前栈顶元素）
            self.min_element = x  # 最小值回原
        else:  # 直接计算
            x = self.min_element + self.my_stack.get_stack_top()
        return x  # 返回真实栈顶值

思路参考

测试代码

# 当然，也许还有别的方法，比如建一个辅助的链表
# 欢迎你说出你的想法

# 程序入口，测试函数功能
if __name__ == "__main__":
    # s = MyStack1()  # 初始化一个MyStack
    s = MyStac2()  # 初始化一个MyStack
    s.push(4)
    s.push(6)
    s.push(2)
    print("栈当前最小元素为：", s.get_min())
    print("当前栈顶元素为：", s.get_top())
    s.pop()
    print("栈当前最小元素为：", s.get_min())
    print("当前栈顶元素为：", s.get_top())
    s.push(1)
    print("栈当前最小元素为：", s.get_min())
    print("当前栈顶元素为：", s.get_top())
    s.push(8)
    print("栈当前最小元素为：", s.get_min())
    print("当前栈顶元素为：", s.get_top())
    s.pop()
    s.pop()
    print("栈当前最小元素为：", s.get_min())
    print("当前栈顶元素为：", s.get_top())

运行结果

本文代码思路大部分来自书籍《Python程序员面试宝典》，书中部分代码有问题，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。

大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。

欢迎关注微信公众号：简说Python
关注后回复：1024，可以领取精选编程学习电子书籍。

最后

以上就是清爽画笔为你收集整理的Smarter Python数据结构：根据入栈序列来判断可能的出栈序列&&利用O(1)的时间复杂度求栈中最小元素的全部内容，希望文章能够帮你解决Smarter Python数据结构：根据入栈序列来判断可能的出栈序列&&利用O(1)的时间复杂度求栈中最小元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。