# 栈和排序
 [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#中等) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#栈队列) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#经典)
> [栈和排序\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f)
**问题简述**
```
给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈
你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列
要求：时间复杂度 O(n)，空间复杂度 O(n)
```
**思路1**
* 题目要求字典序最大，且数组中的元素确定为 `1~n`；
* 因此第一个出栈的元素一定是 `n`；
* 假设当前出栈元素为 `a[i]`，则接下来有两种情况：
* 如果当前栈顶元素大于 `a[i]` 之后的最大值，则循环出栈；
* 否则继续入栈；
* 写法 1 为上述算法的直观实现（每次查找 `a[i+1:n]` 中的最大值），会超时；
* 写法 2 预处理了每个位置之后的最大值（不包含当前位置）；
* 写法 3 是本质上也是上述算法的实现，但是技巧性更强（只遍历一次）；
* 它利用了题目中数组中元素为 `1~n` 这一特点；如果不是这些元素就会出问题；
Python 写法1（超时）
```python
class Solution:
def solve(self , a: List[int]) -> List[int]:
n = len(a)
s = [] # 模拟栈
ret = [] # 保存答案
for i in range(n):
s.append(a[i])
# 如果栈顶元素大于之后的最大值，就出栈，否则跳过
while s and s[-1] >= (mx := max(a[i + 1:] + [float('-inf')])): # 防止 max(空数组)
ret.append(s.pop())
while s:
ret.append(s.pop())
return ret
```
Python 写法2（推荐）
```python
class Solution:
def solve(self , a: List[int]) -> List[int]:
n = len(a)
# 预处理：计算当前位置之后的最大值（不包括当前位置）
book = [0] * n
book[-1] = float('-inf')
for i in range(n - 2, -1, -1):
book[i] = max(book[i + 1], a[i + 1])
# book[i] = max(book[i + 1], a[i]) # 这样写表示包括当前位置，err
s = [] # 模拟栈
ret = [] # 保存答案
for i in range(n):
s.append(a[i])
while s and s[-1] >= book[i]: # book[i] 表示 a[i] 之后的最大值
ret.append(s.pop())
while s:
ret.append(s.pop())
return ret
```
Python 写法3
```python
class Solution:
def solve(self , a: List[int]) -> List[int]:
ret = [] # 记录答案
s = [] # 模拟栈
n = len(a)
book = [0] * (n + 1) # 记录已经出现过的元素
for x in a:
s.append(x)
book[x] = 1
while n and book[n]:
n -= 1
while s and n <= s[-1]:
ret.append(s.pop())
while s:
ret.append(s.pop())
return ret
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/niu-ke-0115-zhong-deng-zhan-he-pai-xu.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.