程序员面试金典 - 面试题 03.05. 栈排序

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

示例 1:

• 输入：
  ["SortedStack", "push", "push", "peek", "pop", "peek"]
  [[], [1], [2], [], [], []]
• 输出：
  [null,null,null,1,null,2]

示例 2:

• 输入：
  ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
  [[], [], [], [1], [], []]
• 输出：
  [null,null,null,null,null,true]

说明:

栈中的元素数目在[0, 5000]范围内。

题目思考

1. 如何利用辅助栈来做到有序, 如何优化?

解决方案

方案 1

思路

• 根据题目描述, 我们可以采用插入排序的思路直接模拟整个过程
• push 的时候使用辅助栈来保证 val 插入到合适的位置, 主栈保持栈顶到栈顶递减的顺序
• 这样 pop 和 push 的时候就可以直接拿到栈顶, 它就是最小值

复杂度

• 时间复杂度
  • peek 和 pop 显然是 O(1)
  • push 需要 O(N)
• 空间复杂度
  • 使用了两个栈存 N 个元素

代码

class SortedStack:
    # 方法1: 模拟, 插入排序思路
    # push的时候使用辅助栈来保证val插入到合适的位置, 主栈保持栈顶到栈顶递减的顺序
    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        temp = []
        while self.stack and self.stack[-1] < val:
            # 将当前栈中小于val的部分先临时存到辅助栈中
            temp.append(self.stack.pop())
        # 找到合适位置了, 将当前val追加到栈顶
        self.stack.append(val)
        while temp:
            # 再将辅助栈的元素倒回来, 保证仍有序
            self.stack.append(temp.pop())

    def pop(self) -> None:
        if self.isEmpty():
            return
        # 主栈有序, 所以直接pop栈顶即可
        self.stack.pop()

    def peek(self) -> int:
        if self.isEmpty():
            return -1
        # 主栈有序, 所以栈顶即为所求
        return self.stack[-1]

    def isEmpty(self) -> bool:
        return not self.stack

方案 2

思路

• 方案 1 在每次 push 时都需要从辅助栈和主栈中来回倒数据, 特别是连续 push 多个较大值时, 效率很低, 因为每次都需要将较大值到栈顶的部分倒入辅助栈, 最后再倒回来, 如何优化这部分操作呢?
• 我们可以持久化存储辅助栈, 避免连续 push 多个值时的来回倒入
• 辅助栈从栈底到栈顶单调递增, 而主栈从栈底到栈顶单调递减, 且辅助栈元素都小于主栈元素
• 这样 push 的时候只需要根据两个栈栈顶的值, 来回倒有限次后就找到了合适的插入位置, 最关键的是连续 push 多个值的时候, 也不需要每次都将该值到最小值之间的部分倒入到辅助栈再倒回来
• 而 pop/peek 的时候则必须要将辅助栈的元素倒入主栈中, 使得主栈栈顶是最小值. 这样也不会降低连续 pop/peek 的性能: 因为第一次 pop/peek 后的主栈就有序了, 之后的 pop/peek 直接拿栈顶即可, 不需要再次倒入

复杂度

• 时间复杂度
  • peek 和 pop 虽然有循环, 但均摊下来仍是 O(1), 因为连续的 peek/pop 只有第一次操作需要循环
  • push 需要 O(N), 但对连续的 push 有所优化
• 空间复杂度
  • 使用了两个栈存 N 个元素

代码

class SortedStack:
    # 方法2: 持久化存储辅助栈, 避免连续push多个值时的来回倒入
    def __init__(self):
        self.stack = []
        self.temp = []

    def push(self, val: int) -> None:
        while self.stack and self.stack[-1] < val:
            # 主栈栈顶小于val, 需要将主栈栈顶元素倒入辅助栈中
            self.temp.append(self.stack.pop())
        while self.temp and self.temp[-1] > val:
            # 辅助栈栈顶大于val, 需要将辅助栈栈顶元素倒入主栈中
            self.stack.append(self.temp.pop())
        # 找到合适位置了, 插入主栈栈顶
        self.stack.append(val)

    def pop(self) -> None:
        if self.isEmpty():
            return
        while self.temp:
            # 将当前辅助栈元素倒入主栈中
            self.stack.append(self.temp.pop())
        # 此时主栈有序, 所以直接pop栈顶即可
        self.stack.pop()

    def peek(self) -> int:
        if self.isEmpty():
            return -1
        while self.temp:
            # 将当前辅助栈元素倒入主栈中
            self.stack.append(self.temp.pop())
        # 此时主栈有序, 所以栈顶即为所求
        return self.stack[-1]

    def isEmpty(self) -> bool:
        return not self.stack and not self.temp

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊