简化路径 图解题解
Unix 路径里的 ..、连续斜杠、结尾斜杠全都要处理——用栈模拟「进一层退一层」，一次扫描就能拿到规范路径。
就像手机导航的「返回上一步」：把路径按斜杠切成一段段目录名，普通目录名往栈里压一层；遇到 .. 就弹出栈顶退回上一层；遇到 . 或空串（来自连续斜杠）直接跳过。最后把栈里剩下的目录名从下到上拼成 / 分隔的字符串，根目录的上级还是根目录——栈空就别弹了。每段只处理一次，不用反复改原字符串。
这道题到底在问什么
- 输入
- path = "/a/./b/../../c/"
- 输出
- "/c"
- 输入
- path = "/../"
- 输出
- "/"
最优解：一步一步想明白
- 3记住这一句，下面每一帧都在套它。空段在图里用 · 标出来。
- 4上排是分好的段（固定不变），下面竖着的是目录栈。指针停在第一段。
- 5第 0 段是空段（连续的 / 切出来的） → 不影响层级，跳过。
- 6第 1 段是目录名「home」→ 进入这一级，入栈。
- 7第 2 段是 "."（当前目录） → 不影响层级，跳过。
- 8第 3 段是目录名「user」→ 进入这一级，入栈。
- 9第 4 段是 ".." → 回到上一级，把栈顶弹出来。
- 10第 5 段是目录名「docs」→ 进入这一级，入栈。
- 11第 6 段是目录名「a」→ 进入这一级，入栈。
- 12第 7 段是目录名「b」→ 进入这一级，入栈。
- 13第 8 段是 ".." → 回到上一级，把栈顶弹出来。
- 14第 9 段是目录名「c」→ 进入这一级，入栈。
- 15第 10 段是 "."（当前目录） → 不影响层级，跳过。
- 16第 11 段是目录名「d」→ 进入这一级，入栈。
- 17第 12 段是 ".." → 回到上一级，把栈顶弹出来。
- 18第 13 段是 ".." → 回到上一级，把栈顶弹出来。
- 19第 14 段是目录名「e」→ 进入这一级，入栈。
- 20第 15 段是目录名「f」→ 进入这一级，入栈。
- 21第 16 段是目录名「g」→ 进入这一级，入栈。
- 22第 17 段是 "."（当前目录） → 不影响层级，跳过。
- 23第 18 段是 ".." → 回到上一级，把栈顶弹出来。
- 24第 19 段是目录名「h」→ 进入这一级，入栈。
- 25第 20 段是空段（连续的 / 切出来的） → 不影响层级，跳过。
- 26第 21 段是目录名「i」→ 进入这一级，入栈。
- 27第 22 段是 ".." → 回到上一级，把栈顶弹出来。
- 28第 23 段是目录名「final」→ 进入这一级，入栈。
- 29所有段处理完，把栈里的目录从底到顶用 / 串起来，就是简化路径 /home/docs/a/e/f/h/final。
- 30关键看 ".." 碰到空栈时的处理。
- 31同一套规则，盯着连续两个 ".." 那两帧。
- 32空段 → 跳过。
- 33「a」是目录名，入栈。
- 34"." → 跳过。
- 35「b」是目录名，入栈。
- 36".." → 弹出栈顶，回上一级。
- 37".." → 弹出栈顶，回上一级。
- 38「c」是目录名，入栈。
- 39连续两个 ".." 把 a、b 都弹掉又遇空栈忽略，最后只剩 c → 答案 /c。
⚠️ 容易写错的地方
✗ 错：".." 时不判栈空
✓ 对：栈空遇 ".." 直接忽略
"/../" 已在根，再回上级会越界/出错
✗ 错：忘了处理空段
✓ 对：连续 / 切出的空段要跳过
"/a//b" 中间的空段不是目录
✗ 错：把 "." 当成目录名入栈
✓ 对："." 是当前目录，跳过
入栈会多出一级假目录
完整代码（Python / C++ / Java）
Python
def simplifyPath(path: str) -> str:
stack = []
for seg in path.split("/"):
if seg == "" or seg == ".":
continue
if seg == "..":
if stack: stack.pop()
else:
stack.append(seg)
return "/" + "/".join(stack)C++
string simplifyPath(string path){
vector<string> stack;
stringstream ss(path); string seg;
while(getline(ss, seg, '/')){
if(seg=="" || seg==".") continue;
if(seg==".."){ if(!stack.empty()) stack.pop_back(); }
else stack.push_back(seg);
}
string res;
for(auto& s : stack) res += "/" + s;
return res.empty() ? "/" : res;
}Java
String simplifyPath(String path){
Deque<String> stack = new ArrayDeque<>();
for(String seg : path.split("/")){
if(seg.isEmpty() || seg.equals(".")) continue;
if(seg.equals("..")){ if(!stack.isEmpty()) stack.pollLast(); }
else stack.offerLast(seg);
}
StringBuilder sb = new StringBuilder();
for(String s : stack) sb.append("/").append(s);
return sb.length()==0 ? "/" : sb.toString();
}复杂度
时间
O(n)
每段处理一次，进出栈各至多一次
空间
O(n)
最坏全是目录名，都压进栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 简化路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用栈而不是直接字符串拼接？+
".." 需要撤销“最近一次进入的目录”，栈天然支持“弹出最近一个”，正好对应回上级；字符串拼接还要回头找上一个 / 很麻烦。
结果末尾要不要带 /？+
不带。规范路径除根 "/" 外，任何目录后面都不跟 /；用 "/" + join(stack) 拼接天然满足，空栈时单独返回 "/"。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 简化路径 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。