Coding Interviews 30 可 O(1) 查找最小值的栈

题目

题目链接
题目概述：自定义一个栈结构，添加可找到最小值的方法 min()，并要求其 min()，push()，pop() 方法都得在 O(1) 完成

思考点

O(1) 时间复杂度这就要求了你不可能在每次 push 新元素的时候，通过排序去维护一个有序数组。且 min 方法也不能动态地找出当前最小值。
存储结构两种常见的方式，存数据还是存索引？这里也许不是很必要。在看了官方题解后，我才意识到还需要考虑存储数据类型。
存储数据类型有序列表还是最小值本身？其实自己思路的一开始都是以有序列表为基础的，但随后才发现有序列表的维护很难在 O(1) 完成。且题解给到的对最小值本身的栈存储，才让自己清醒，你需要的仅仅是对当前集合状态最小值的保存。

题解

最小值栈记录当前状态

instance variable 中的 data_stack 存储栈本身的数据，由 min_stack 存储当前状态下的最小值信息。

补充解释当前状态等于当前栈大小。并且弹出 min_stack 不影响其底下元素有效性。

import sys


class MinStack:

    def __init__(self):
        self.data_stack = []
        self.min_stack = []
        self.min_stack.append(sys.maxsize)

    def push(self, x: int) -> None:
        self.data_stack.append(x)
        cur_min = self.min_stack[len(self.min_stack)-1]
        if x < cur_min:
            self.min_stack.append(x)
        else:
            self.min_stack.append(cur_min)

    def pop(self) -> None:
        self.data_stack.pop()
        if len(self.min_stack) > 1: # 避免弹出 sys.maxsize
            self.min_stack.pop()

    def top(self) -> int:
        return self.data_stack[len(self.data_stack)-1]

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

头插链表并存储当前状态最小值

思路来自评论区 Top1。

Node 节点分别存储新加节点值以及当前状态下的最小值，并且由头插法实现 push 方法。

class Node:

    def __init__(self, data: int, min: int, next):
        self.data = data
        self.cur_min = min
        self.next = next


class MinStackLinked:

    def __init__(self):
        self.head = None

    def push(self, x: int) -> None:
        if self.head is None:
            self.head = Node(x, x, None)
        else:
            # 头插
            self.head = Node(x, min(self.head.cur_min, x), self.head)

    def pop(self) -> None:
        self.head = self.head.next

    def top(self) -> int:
        return self.head.data

    def min(self) -> int:
        return self.head.cur_min

PriorityQueue

思路来自评论区 Top2。

该方法不符合题目要求，因其只有插入效率为 O(1)，而弹出效率为 O(n)。但这种有趣的思路值得借鉴。

优先队列定义：

每个元素都有自己的优先级；
优先级最高的元素先得到服务；
同等优先级的元素按照其插入顺序得到服务；

备注一个从 geeksforgeeks 摘抄的比喻：

For example, In airlines, baggage with the title “Business” or “First-class” arrives earlier than the rest.