[面试题 03.05][中等] 栈排序

题目描述

面试题 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]范围内。

解题思路

由于最小的元素要位于栈顶, 相当于栈内的元素是有顺序的. 因此在压入一个新元素时, 需要将这个元素与栈顶元素依次比较, 将小于这个元素的栈顶元素依次弹出, 然后放入一个辅助栈中, 压入这个新元素后再将辅助栈的元素压回.

因为栈的性质, 反复调整两次, 元素的顺序仍然是不变得.

这样除了push操作的时间复杂度是$O(n)$, 其他操作的时间复杂度都是$O(1)$.

class SortedStack:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, val: int) -> None:
        while self.stack1 and self.stack1[-1] < val:
            self.stack2.append(self.stack1.pop())
        self.stack1.append(val)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    def pop(self) -> None:
        return self.stack1.pop() if self.stack1 else None

    def peek(self) -> int:
        return self.stack1[-1] if self.stack1 else -1

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


# Your SortedStack object will be instantiated and called as such:
# obj = SortedStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.peek()
# param_4 = obj.isEmpty()