栈和排序

[编程题]栈和排序

热度指数：9614 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈

你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列

排列：指 1 到 n 每个数字出现且仅出现一次

数据范围： $1 \le n \le 5 \times 10^4$ ，排列中的值都满足 $1 \le val \le n$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

[2,1,5,3,4]

输出

[5,4,3,1,2]

说明

操作       栈     结果
2 入栈；[2]       []
1 入栈；[2\1]     []
5 入栈；[2\1\5]   []
5 出栈；[2\1]     [5]
3 入栈；[2\1\3]   [5]
4 入栈；[2\1\3\4] [5]
4 出栈；[2\1\3]   [5,4]
3 出栈；[2\1]     [5,4,3]
1 出栈；[2]       [5,4,3,1]
2 出栈；[]        [5,4,3,1,2]

示例2

输入

[1,2,3,4,5]

输出

[5,4,3,2,1]

算法知识视频讲解

Python3

liangzhengjie

from operator import index
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 栈排序
# @param a int整型一维数组 描述入栈顺序
# @return int整型一维数组
#
class Solution:
    def solve(self , a: List[int]) -> List[int]:
        # write code here
        if len(a) == 0&nbs***bsp;len(a) == 1:
            return a

        stack = []
        stack.append(a[0])
        res = []

        # 构建右视图最大表
        right_max = [0 for i in range(len(a))]
        right_max[-1] = a[-1]
        for i in range(len(a)-2, -1, -1):
            right_max[i] = max(a[i], right_max[i + 1])

        index = 1
        while index < len(a):
            if len(stack) == 0:
                stack.append(a[index])
                index += 1
                continue

            # 栈顶大于入栈数，将栈顶加入结果
            if stack[-1] >= right_max[index]:
                res.append(stack[-1])
                stack.pop()
            else:
                stack.append(a[index])
                index += 1

        while len(stack) != 0:
            res.append(stack[-1])
            stack.pop()


        return res

编辑于 2024-03-29 23:15:52 回复(0)