> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/niu-ke-0115-zhong-deng-zhan-he-pai-xu.md).

# 栈和排序

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E6%A0%88/%E9%98%9F%E5%88%97\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#栈队列) [![](https://img.shields.io/static/v1?label=\&message=%E7%BB%8F%E5%85%B8\&color=blue\&style=flat-square)](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` 这一特点；如果不是这些元素就会出问题；

<details>

<summary><strong>Python 写法1（超时）</strong></summary>

```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
```

</details>

<details>

<summary><strong>Python 写法2（推荐）</strong></summary>

```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
```

</details>

<details>

<summary><strong>Python 写法3</strong></summary>

```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
            
```

</details>