题解 | #栈和排序#

题目要求：按序入栈，输出最大字典序的出栈结果。换言之，查找a[i]后最大的数max，当max<a[i]时，将a[i]出栈，然后反向检索辅助栈将大于max的一并出栈；当max>=a[i]时，将a[i]入栈到辅助栈。

思路流程：

• 构造辅助数组temp， temp[i]表示a[i+1:]中的max。其中temp的实现比较巧妙。temp[-1]=-inf，反向遍历a[:-2]，取max(a[i+1],temp[i+1])作为temp[i]的值，因为temp[i+1]表示a[i+2:]的max，所以a[i+1:]的max可以通过a[i+1]和temp[i+1]比较获得，一种dp思想。
• 构造辅助栈stack，用来存放暂不出栈的元素，以及实现后续连续出栈

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 栈排序
# @param a int整型一维数组 描述入栈顺序
# @return int整型一维数组
#
class Solution:
    def solve(self , a: List[int]) -> List[int]:
        # write code here
        temp=[0]*len(a)
        temp[-1]=-float('inf')
        stack=[]
        res=[]
        for i in range(len(a)-2,-1,-1):
            temp[i]=max(a[i+1],temp[i+1])
        for i in range(len(a)):
            if a[i]<=temp[i]:
                stack.append(a[i])
            else:
                res.append(a[i])
                while stack and stack[-1]>temp[i]:
                    res.append(stack.pop())
        return res