栈和排序

[编程题]栈和排序

热度指数：9581 时间限制：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]

算法知识视频讲解

Python

VincentLau~

#
# 栈排序
# @param a int整型一维数组 描述入栈顺序
# @return int整型一维数组
#
class Solution:
    def solve(self , a ):
        # write code here
        n, stack, dp, res = len(a), [], [0]*len(a), []
        dp[-1] = a[-1] # 记录从第i个元素开始到最后的最大元素
        for i in range(n-2, -1, -1):
            dp[i] = max(dp[i+1], a[i])
        for i in range(n):
            stack.append(a[i])
            while stack and i < n-1 and stack[-1]>=dp[i+1]:
                res.append(stack.pop()) # 如果栈顶元素比后面所有元素都大，则弹出
        while stack:
            res.append(stack.pop())
        return res

发表于 2021-06-24 14:49:05 回复(0)

Python

SaraNova

class Solution:
def solve(self , a ):
# write code here
n = len(a)
if n == 0:
return []
max_right = [0]*n
max_right[n-1] = -1
maxo = a[n-1]
for i in range(n-2,-1,-1):
max_right[i] = maxo
if a[i] > maxo:
maxo = a[i]
queue = []
ans = []
for i in range(n):
queue.append(a[i])
while len(queue)-1 >=0 and queue[len(queue)-1] >= max_right[i]:
ans.append(queue.pop())

while len(queue)!=0:
ans.append(queue.pop())
return ans

发表于 2021-06-02 16:03:25 回复(0)