最小栈

Leetcode Link: 155. 最小栈 - 力扣（LeetCode） 剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素 val 推入堆栈。
• void pop() 删除堆栈顶部的元素
• int top() 获取堆栈顶部的元素
• int getMin() 获取堆栈中的最小元素

解法一

思路： 用普通的 list 和 SortedList 打配合即可。(有的题解成为辅助栈和数据栈)

普通的 list 用作栈，保存谁先谁后的信息 SortedList 用来进行排序

题解：

from sortedcontainers import SortedList
class MinStack:
 
    def __init__(self):
        self.stack = []
        self.sortlst = SortedList()
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        self.sortlst.add(val)
 
    def pop(self) -> None:
        val = self.stack.pop()
        self.sortlst.remove(val)
        return val
 
    def top(self) -> int:
        return self.stack[-1]
 
    def getMin(self) -> int:
        return self.sortlst[0]

解法二

思路 使用链表，多定义一个属性，mini，用来保存当前节点之前（含该节点）的最小值

题解

class Node:
    def __init__(self, val=0, pre=None, next=None):
        self.val = val
        self.pre = pre
        self.next = next
        self.mini = float('inf')
 
class MinStack:
 
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.head = Node()
        self.tail = Node(pre=self.head)
        self.head.next = self.tail
        
    def push(self, x: int) -> None:
        node = Node(val=x, next=self.tail, pre=self.tail.pre)
        if x < self.tail.pre.mini:
            node.mini = x
        else:
            node.mini = self.tail.pre.mini
        
        self.tail.pre.next = node
        self.tail.pre = node
 
    def pop(self) -> None:
        if self.tail.pre.mini == float('inf'):
            return None
        res = self.tail.pre.val
        self.tail.pre.pre.next = self.tail
        self.tail.pre = self.tail.pre.pre
        return res
 
    def top(self) -> int:
        if self.tail.pre.mini == float('inf'):
            return None
        res = self.tail.pre.val
        return res
 
    def getMin(self) -> int:
        return self.tail.pre.mini

启发和联系

更多关于SortedList 的用法可以参考设计食物评分系统