LeetCode 71中等栈
简化路径 图解题解
Unix 路径里的 ..、连续斜杠、结尾斜杠全都要处理——用栈模拟「进一层退一层」，一次扫描就能拿到规范路径。
就像手机导航的「返回上一步」：把路径按斜杠切成一段段目录名，普通目录名往栈里压一层；遇到 .. 就弹出栈顶退回上一层；遇到 . 或空串（来自连续斜杠）直接跳过。最后把栈里剩下的目录名从下到上拼成 / 分隔的字符串，根目录的上级还是根目录——栈空就别弹了。每段只处理一次，不用反复改原字符串。
这道题到底在问什么
给一个 Unix 绝对路径，处理「当前目录」「上级目录」、连续斜杠和结尾斜杠，返回规范路径。
- path
- "/a//b/./../c/"
- 输出
- "/a/c"
- 规则
- 根目录的上一级仍是根目录
最优解：一步一步想明白
- 3最直觉的办法是找到「目录加上级目录」这种片段直接删掉。但删完还要重新扫描，连续斜杠会制造空段，开头就是上级目录时又不能继续往上退。真正的难点是：上级目录只应该撤销最近进入的那一层。
- 4栈顶永远是最近进入的目录。普通目录名入栈，表示深入一层；遇到上级目录就弹出栈顶，表示退回上一层；遇到当前目录或空段直接跳过。这样每一段只处理一次，不需要反复改字符串。
- 5path = "/a//b/./../c/"先把路径按斜杠切开。开头、连续斜杠和结尾斜杠会切出空串，这里用引号空串表示。接下来从左到右逐段处理。
- 6当前路径 /a读到 a，普通目录名，入栈。栈就是当前路径，现在是 /a。
- 7栈不变 · /a读到空串，它来自连续斜杠，不是目录，跳过。栈仍然是 /a。
- 8当前路径 /a/b读到 b，入栈。路径深入到 /a/b，栈顶 b 就是最近进入的那一层。
- 9原地不动 · /a/b读到单点，它表示「当前目录」，既不深入也不回退。画面不变，栈顶仍然是 b。
- 10当前路径 /a/b读到上级目录，要回退一层。最近进入的是谁？就是栈顶 b。先看清楚，下一帧再弹。
- 11回到 /a弹出栈顶 b。路径从 /a/b 回到 /a。只动栈顶，不会误删更早进入的 a。
- 12当前路径 /a/c读到 c，普通目录，入栈。栈现在是 a、c 两层。
- 13答案 = "/a/c"处理完了。把栈里的目录从底到顶用斜杠拼起来，前面补一个根斜杠，得到 "/a/c"。如果栈为空，就单独返回一个斜杠。
- 14/a → /a/b → 遇上级 → /a → /a/c把整条路重放一遍：进入 a、进入 b，遇上级弹掉 b 回到 a，再进入 c。栈的高度就是路径的深度，栈顶就是当前所在目录。
- 17记住这句话，上级目录为什么弹、普通目录为什么压、最后为什么拼，就都顺了：栈从底到顶正好是根目录往下走过的标准路径。
- 19path = "/../x"危险样例：路径一开头就是上级目录。栈为空，说明现在就在根目录；根的上一级还是根，这一步必须跳过，不能弹空栈。
- 20答案 = "/x"继续读 x，普通目录入栈，最后结果是 "/x"。这两帧把「空栈遇上级目录」从文字坑变成了可见动作。
- 25凡是「进入一层、退出一层、最近进入的先退出」的题，都在用同一个栈思想：简化路径练目录层级、括号匹配练符号层级、基本计算器练表达式层级。想系统刷可以让小欧带你打通 栈专题。
⚠️ 容易写错的地方
✗ 错：遇上级目录直接 pop
✓ 对：栈非空才 pop
根目录再往上还是根，空栈不能弹。
✗ 错：把三个点当特殊段
✓ 对：只有单点和双点特殊
三个点、点开头的隐藏目录都是普通目录名。
✗ 错：空串入栈
✓ 对：空串永远跳过
开头斜杠、连续斜杠、结尾斜杠都会切出空串。
完整代码（Python / C++ / Java）
Python
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for part in path.split("/"):
if part == "" or part == ".":
continue
if part == "..":
if stack:
stack.pop()
else:
stack.append(part)
return "/" + "/".join(stack)C++
class Solution {
public:
string simplifyPath(string path) {
vector<string> st;
string part;
stringstream ss(path);
while (getline(ss, part, '/')) {
if (part.empty() || part == ".") continue;
if (part == "..") {
if (!st.empty()) st.pop_back();
} else {
st.push_back(part);
}
}
string ans;
for (auto &dir : st) ans += "/" + dir;
return ans.empty() ? "/" : ans;
}
};Java
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
for (String part : path.split("/")) {
if (part.isEmpty() || part.equals(".")) continue;
if (part.equals("..")) {
if (!stack.isEmpty()) stack.removeLast();
} else {
stack.addLast(part);
}
}
return "/" + String.join("/", stack);
}
}套路模板 · 层级回退栈（挖空背骨架）
stack = []
for part in parts: # parts 由斜杠切分得到
if part in ("", "."): # ① 忽略项：空段 / 原地
continue
if part == "..": # ② 回退项：空栈不弹
if stack: stack.pop()
else: # ③ 入栈项：深入一层
stack.append(part)
return "/" + "/".join(stack) # 栈底到顶 = 绝对路径vector<string> st;
for (string part : parts) { // parts 由斜杠切分得到
if (part.empty() || part==".") continue; // ① 忽略项
if (part == "..") { // ② 回退项：空栈不弹
if (!st.empty()) st.pop_back();
} else { // ③ 入栈项
st.push_back(part);
}
}
string ans;
for (auto &d : st) ans += "/" + d; // 栈底到顶 = 绝对路径
return ans.empty() ? "/" : ans;Deque<String> stack = new ArrayDeque<>();
for (String part : parts) { // parts 由斜杠切分得到
if (part.isEmpty() || part.equals(".")) continue; // ① 忽略
if (part.equals("..")) { // ② 回退项：空栈不弹
if (!stack.isEmpty()) stack.removeLast();
} else { // ③ 入栈项
stack.addLast(part);
}
}
return "/" + String.join("/", stack); // 栈底到顶 = 路径复杂度
时间复杂度
O(n)
n 是路径长度。切分扫一遍；每个目录段最多入栈一次、出栈一次，总操作不超过 2n 量级，所以是线性。
空间复杂度
O(n)
最坏没有任何上级目录，所有目录段都留在栈里，例如 /a/b/c/d，栈和输出都是 O(n)。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 简化路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不用字符串替换？+
替换要反复扫描；开头就是上级目录这种根边界很难写稳，栈一次扫描就解决。
三个点怎么办？+
当普通目录名入栈。只有单点和双点两个精确字符串特殊。
栈空时遇上级目录为什么不弹？+
已经在根目录，根目录的上一级仍然是根目录，弹空栈会出错。
能不先切分吗？+
可以边扫描边按斜杠收集每一段，本质仍是同一个目录栈。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。