华为 · 栈 · 算法编程题
华为 栈 n ≤ 10 时限 1 秒 / 32 MB

题目描述

火车站一共有 n 辆火车需要入站，每辆火车有一个编号，编号为 1 到 n 。
同时，也有火车需要出站，由于火车站进出共享一个轨道，所以后入站的火车需要先出站。换句话说，对于某一辆火车，只有在它之后入站的火车都出站了，它才能出站。
现在，已经知道了火车的入站顺序，你需要计算，一共有多少种不同的出站顺序。按照字典序从小到大依次输出全部的出站顺序。

输入输出

输入描述
第一行输入一个整数 n (1 ≤ n ≤ 10) 代表火车的数量。
第二行输入 n 个整数 a_1,a_2,...,a_n (1 ≤ a_i ≤ n) 代表火车的入站顺序。
输出描述
输出若干行，每行输出 n 个整数，代表一种出站顺序。你需要按照字典序从小到大依次输出。

样例共 1 组

样例 1 · 在这个样例中，每一种出栈顺序的详细出入站状况为（黑色普通字体代表入站、橙色加粗字体代表出站）： 1 → orange 1 → 2 → orange 2 → 3 → orange 3 ； 1 → orange 1 → 2 → 3 → orange 3 → orange 2 ； 1 → 2 → orange 2 → orange 1 → 3 → orange 3 ； 1 → 2 → orange 2 → 3 → orange 3 → orange 1 ； 1 → 2 → 3 → orange 3 → orange 2 → orange 1 。
输入
3
1 2 3
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

算法解析依据充分

考点：栈

数据规模 n ≤ 10 ｜ 限制 1 秒 / 32MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 10
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：栈

后进先出的结构天然适合处理嵌套、匹配与「最近的更大/更小」问题。

思路框架（栈 通法 · 非本题专属）

  1. 括号匹配：遇左括号入栈，遇右括号检查栈顶是否配对。
  2. 单调栈：从左到右扫，维持栈内单调，遇到破坏单调性的元素就弹栈并结算答案。
  3. 每个元素最多进出栈各一次，总复杂度 O(n)。

实现要点：Python 用 list 当栈（append/pop）；判断栈空再取栈顶。

复杂度：时间 O(n) ｜ 空间 O(n)

该范式的通法易错点

  • 栈空时取栈顶。
  • 弹栈时机的判断条件写反。

对照本题

  • 数据规模 n ≤ 10，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。

样例解读

样例 1：输入 3 / 1 2 3 → 输出 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 2 1

在这个样例中，每一种出栈顺序的详细出入站状况为（黑色普通字体代表入站、橙色加粗字体代表出站）：

1 → orange 1 → 2 → orange 2 → 3 → orange 3 ；

1 → orange 1 → 2 → 3 → orange 3 → orange 2 ；

1 → 2 → orange 2 → orange 1 → 3 → orange 3 ；

1 → 2 → orange 2 → 3 → orange 3 → orange 1 ；

1 → 2 → 3 → orange 3 → orange 2 → orange 1 。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：华为机试编程模拟题3。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解