面试题 03.05. 栈排序

Difficulty
Medium
Tags
单调栈
URL
https://leetcode.cn/problems/sort-of-stacks-lcci/
Star
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：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]
说明:
  1. 栈中的元素数目在[0, 5000]范围内。
通过次数20,987提交次数38,914

单调栈

思路
每当要进行push操作时，对比待插入值与栈顶元素值的大小，若栈顶值较小就把栈顶元素逐个弹出到辅助栈help中，在合适的位置插入val；
把辅助栈help中的元素全都倒回原栈stk中，即可保持栈有序。
题解
class SortedStack:

    def __init__(self):
        self.minstack = []
        self.tempstack = []


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

        while self.tempstack:
            self.minstack.append(self.tempstack.pop())
        

    def pop(self) -> None:
        if self.isEmpty():
            return 
        self.minstack.pop()


    def peek(self) -> int:
        if self.isEmpty():
            return -1
        return self.minstack[-1]


    def isEmpty(self) -> bool:
        return len(self.minstack) == 0


# 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()