牛客题霸 栈和排序_牛客栈和排序python

题目描述

给你一个1->n的排列和一个栈，入栈顺序给定

你要在不打乱入栈顺序的情况下，对数组进行从大到小排序

当无法完全排序时，请输出字典序最大的出栈序列

 

示例1

输入

[2,1,5,3,4]

返回值

[5,4,3,1,2]

 

说明

2入栈；1入栈；5入栈；5出栈；3入栈；4入栈；4出栈；3出栈；1出栈；2出栈

 

备注:

n<=1e6

 

Python代码：

#
# 栈排序
# @param a int整型一维数组 描述入栈顺序
# @return int整型一维数组
#
class Solution:
    def solve(self , a ):
        # write code here
        s = []
        n = len(a)
        res = []
        vis = [0] * (n+1)
        for x in a:
            s.append(x)
            vis[x] = 1
            while n and vis[n]:
                n -= 1
            while s and n <= s[-1]:
                res.append(s[-1])
                s.pop()
        while s:
            res.append(s[-1])
            s.pop()
        return res