栈的应用：力扣71题简化路径全解析（Python+Java）

力扣第71题简化路径是我刷题时反复看了好几遍的一道中等题。说它简单吧核心逻辑确实就十几行说它难吧它在一堆边界条件上藏了不少坑稍不注意就是连续三个提交翻车。我当时先写了 Python 版觉得稳了结果/...这个用例直接让我清醒换 Java 实现时又因为栈的遍历顺序问题输出反了。这篇文章把这道题的完整思路、双语言实现方式、以及我实测过的所有边界场景都整理出来。如果你想准备算法面试或者刚学完栈想找一道实战题练手这篇笔记值得从头看到尾。1. 题目拆解三个规则读懂简化路径1.1 一上来先搞清楚路径到底怎么走题目输入是一个 Unix 风格绝对路径比如/a/./b/../../c/要求输出简化后的结果。要理解这题得先建立目录栈的直觉。你在终端里执行cd /a/b实际上就是从根目录往下走两级执行cd ..就是往回退一级。题目里的.表示当前目录..表示上一级目录连在一起的//只算一个分隔符。官方几个示例很能说明问题/home/简化后是/home末尾多余的斜杠去掉。/../简化后是/根目录的上一级还是根目录。/home//foo/简化后是/home/foo连续斜杠被合并。简化后的路径必须满足四个约束以单个/开头目录之间只保留一个/不以/结尾除非整个路径就是根目录/路径里不允许出现.和..这样的成分。我一开始以为这就是字符串清洗把多余的斜杠删掉、把.段删掉、把..段连同前面的目录一起删掉就行了。后来发现真正的难点在于删除这个动作怎么组织才不出错尤其是连续多个..的情况。这题本质上是在考察你对层级关系的建模能力而不是字符串处理能力。1.2 最容易被忽略的规则什么才是合法目录名题目里有一句很多人会扫过去的关键描述任何其他形式的点比如...都要当作合法目录名处理。这句话直接决定了一个经典用例输入/...输出依然是/...而不是/或者报错。为什么这是坑因为很多人在写判断时习惯用if part ..和if part .两个分支这没问题。但如果你用的是包含点就跳过这种笼统逻辑比如if . in part: continue那...、.hidden、a.b这些合法目录名就全被误杀了。更隐蔽的是.hidden这种以点开头的文件在 Linux 里是隐藏文件作为目录名完全合法a.b这种中间带点的目录名也合法。所以正确的判断逻辑必须是精确相等而不是包含关系。还有一个容易忽略的点..在栈为空时应该怎么处理比如输入/../栈里什么都没有这时候..想往上跳总不能跳出一个不存在的位置。正确做法是直接忽略它什么都不做。这一点也对应了根目录的父目录还是根目录这条隐含规则。2. 思路对比正则替换、手动扫描与切分栈2.1 我一开始想用正则后来放弃了拿到题目时我脑子里冒出的第一个方案是用正则或者字符串替换先把//替换成/再处理.和..。但这个思路在实操中很快暴露问题。第一个问题替换顺序很难定。如果你先把//替换成/再去掉.段那/a/./b/变成/a/b/之后还得再处理结尾斜杠。如果是/a/././b连续多个.段也还好但一旦混进..比如/a/b/../c你需要向前删一个目录这用纯字符串替换根本没法表达。第二个问题..是连续的、有状态的。/a/b/c/../../..对应的是先删c再删b最后删a一直退到根。这种根据之前入过的目录决定删除目标的逻辑只有用栈或者类似的线性数据结构才能自然表达。正则是一种无状态匹配工具用它做有状态操作代码只会越写越扭曲。所以我最终放弃了正则路线。这个试错过程也有价值它让我明白刷题时先判断题目背后的数据结构需求比先想字符串技巧更重要。2.2 用栈模拟目录栈的完整推演栈方案的核心思想非常直白把路径按/切分成若干段然后遍历每一段用栈记录当前所在位置。遇到普通目录名就压栈遇到..就弹栈如果栈非空遇到.或者空字符串就跳过。最后把栈里的目录名用/拼起来。拿官方示例/a/./b/../../c/手动推演一遍。按/切分后得到[, a, ., b, .., .., c, ]然后逐个处理当前段动作栈内容空串跳过[]a普通目录入栈[a].当前目录跳过[a]b普通目录入栈[a, b]..上一级弹出 b[a]..上一级弹出 a[]c普通目录入栈[c]空串跳过[c]遍历结束后栈里只剩c拼接结果是/c和题目输出完全一致。整个过程不需要回头看也不需要预判后续段每一段只根据当前栈的状态做一次入栈或出栈操作。这就是栈结构最典型的应用场景匹配、回溯、撤销这类反向操作。2.3 时间与空间复杂度为什么是最优分析复杂度时首先要明确 n 的定义。这里 n 是输入路径字符串的长度。split操作本身要遍历整个字符串时间复杂度 O(n)切分后得到的每一段只被处理一次入栈、出栈都是 O(1) 的数组操作。所以总时间复杂度是 O(n)。空间上栈里最多存储所有目录段即切分结果的规模同样不超过 O(n)所以空间复杂度是 O(n)。可能有人会问能不能做到 O(1) 空间如果你允许原地修改字符串并且不需要保存中间目录理论上可以但那样代码复杂度会大幅上升而且面试时没必要。对于这道题O(n) 时间和 O(n) 空间就是最优、也最简洁的平衡点。面试官问我为什么不用手动指针逐个字符扫描时我的回答是切分加栈已经覆盖了所有边界情况手动扫描反而要自己处理连续斜杠、段边界、空串这些细节更容易出错。代码的可读性和正确性比省一个循环更重要。3. 双语言实现Python三行核心逻辑Java注意输出顺序3.1 Python版本短而清晰的参考写法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)这里最关键的两个点一是判断必须用精确相等不能把...误判成..或.二是if stack的判断不能省它保证栈为空时遇到..不会抛异常而是静默忽略。/.join(stack)是 Python 里非常顺手的拼接方式。如果栈为空join结果是空字符串前面加一个/就成了根目录/刚好满足根目录单独返回/的要求。我自己做这题时的习惯是先在本地跑一遍官方五个示例再跑几个自己想出来的怪用例比如/...和/a//b////c/d//././/..。这套流程走完Python 版基本就不会翻车了。3.2 Java版本ArrayDeque和Stack怎么选Java 版本的思路和 Python 完全一致但有两个实现上的坑。第一个是容器选择。虽然题解里经常写Stack但它是早期遗留类继承了 Vector所有方法都加锁性能不占优势官方文档也建议优先用ArrayDeque或Deque接口。所以我的参考写法用的是Dequeclass Solution { public String simplifyPath(String path) { DequeString stack new ArrayDeque(); for (String part : path.split(/)) { if (part.isEmpty() || part.equals(.)) { continue; } if (part.equals(..)) { if (!stack.isEmpty()) { stack.pop(); } } else { stack.push(part); } } StringBuilder sb new StringBuilder(); while (!stack.isEmpty()) { sb.append(/).append(stack.removeLast()); } return sb.length() 0 ? / : sb.toString(); } }第二个坑就是输出顺序。我一开始用while (!stack.isEmpty()) { sb.append(/).append(stack.pop()); }想着把元素从头弹出来拼就行。但push是往头部插入pop也是从头部弹出这样一来栈里存的顺序是反的。比如处理完a、b两个目录栈里从头部到尾部是b - a用pop拼出来的结果是/b/a正好和正确答案/a/b相反。正确做法是用removeLast()从尾部取元素或者在入栈时就用addLast()、出栈时用removeLast()来模拟按顺序入队的效果。我的建议是统一记住一个模式如果用的是push拼结果时就必须用removeLast。3.3 不同语言split行为的坑点同样一句path.split(/)Python 和 Java 的行为细节有差异虽然最终不影响这份代码的正确性但理解清楚能避免不少困惑。Python 的split(/)会保留所有空串。比如/.split(/)结果是[, ]/a/.split(/)结果是[, a, ]。这意味着切分结果里可能包含多个空字符串所以代码里必须处理空串的情况。Java 的split(/)默认会丢弃末尾的空字符串。/a/.split(/)结果是[, a]最后那个空串被丢弃了。更特殊的是/.split(/)在 Java 中返回一个长度为零的数组循环压根不会执行。我们的代码对空串和.都做跳过处理所以不管 split 返回的是[, a, ]还是[, a]最终结果一致。但如果你是新手第一次看 Java 的 split 返回结果可能以为代码写错了这里提前打个预防针。如果你的面试语言是 Java建议在写完后主动提一句这里 split 会丢掉尾部的空串我们对空串做了防御性判断所以不受影响面试官会觉得你对语言细节很敏感。4. 边界测试实录这几个用例让很多提交翻车4.1 三个点...不是..最经典的误判陷阱这个坑我专门拿出来说因为它在讨论区出现的频率极高。很多人的第一版代码长这样for part in path.split(/): if part : continue if .. in part: if stack: stack.pop() else: stack.append(part)看起来没问题但.. in ...在 Python 中是 True所以/...会被错误地当成..处理最终输出/而正确答案应该是/...。...是一个合法的目录名文件名里出现多个点非常正常。判断..必须用精确相等这一点无论如何强调都不为过。顺带一提.hidden这种目录也不能被误杀。有些写法会用part[0] .来判断是不是特殊目录这在测试用例/.hidden上会失败。正确逻辑只有一个标准遇到.跳过遇到..出栈遇到其他任何字符串都入栈包括以点开头、中间带点的字符串。4.2 连续斜杠与结尾斜杠split帮你处理了大半连续斜杠的问题比如/home//foo/如果你手动扫描字符需要自己维护当前是否在一个空段中的状态。但用 split 就简单了//切分后会产生一个空串空串被跳过等价于把多个连续斜杠压缩成一个。结尾斜杠同理。/home/切分后最后一个空串被跳过栈里只剩home拼出来是/home。看到没有你不需要额外写去掉末尾斜杠的逻辑切分和跳过空串两步组合起来就解决掉了。不过有一个细节值得留意如果结尾是..或者普通目录名比如/home/foo/..切分后最后一段是..它会把foo弹出去最终结果/home。这是符合题意的因为foo目录其实已经被退出了。4.3 根目录、空路径与栈空时的..根目录是最容易出错的边界。输入/时Python 切分出两个空串Java 切分出零段无论哪种情况栈都是空的最终返回/ .join或sb.length() 0 ? /结果都是/。这里的实现细节是拼接结果是空字符串时要兜底返回/。栈空时遇到..也必须忽略。比如输入/../切分后只有空串和..栈始终为空..什么都不做最后返回/。如果代码写成stack.pop()而不加空栈判断Python 会抛IndexErrorJava 会抛NoSuchElementException提交直接报运行时错误。关于空路径题目保证绝对路径以/开头所以严格来说不会输入空字符串。但作为防御性编程处理空串返回/也不会有问题。面试时可以稍稍提一句显得你考虑边界比题目要求的更全面。4.4 一份可直接复用的测试用例速查表我自己写题时会把下面这些用例存成一个测试清单做任何栈相关题目都能拿来参考。这里直接分享出来输入期望输出验证点/home//home去掉末尾斜杠/..//栈空时..被忽略/home//foo//home/foo连续斜杠合并/a/./b/../../c//c综合入栈出栈/a/../../b/../c//.///c多次..加混合场景/a//b////c/d//././/../a/b/c官方复杂示例/.../...三点是合法目录名/.hidden/.hidden点开头的隐藏目录合法//根目录/a/../../..溢出到根后忽略这套用例跑完代码的正确性基本就有保障了。我在实际提交前会把这十组用例全部过一遍宁可多花两分钟也不要反复提交浪费等待时间。5. 套路迁移从简化路径看栈类题目的通用解法5.1 栈类题目的识别信号做完第71题后我回头总结了一下发现很多栈类题目都有相似的特征。识别信号有三个一是题目里出现撤销回退取消上一步等动作比如括号匹配的右括号要撤销左括号、..要撤销上一级目录二是出现嵌套或层级结构比如路径的目录层级、表达式中的括号层级三是操作顺序是从左到右且当前的决策依赖历史状态。第71题完美命中前两条..是明确的回退操作路径是明确的层级结构。所以当你读完题发现这两个信号第一反应就应该是这题大概率用栈。这个识别能力比记住某一道题的解法更重要。我后来又做了一系列堆栈相关的题目包括括号匹配、逆波兰表达式求值、基本计算器、最长绝对路径等等用的都是同一套思维框架。刷题刷到后面你会发现所谓套路就是对数据结构适用场景的敏感度。5.2 相似题目与变体扩展如果想把栈的套路练透建议按这个顺序做几道题先做括号匹配理解栈的配对作用再做逆波兰表达式求值理解栈的延迟计算作用然后回到这题理解栈的层级回退作用最后可以做最长绝对路径那题会用一个栈保存每一层的长度算是一道综合应用题。第71题本身也有不少变体值得思考。比如输入不是以/开头的相对路径而是./a/../b这种处理逻辑基本不变只需要考虑开头是否要补一个/。再比如 Windows 风格路径用反斜杠\分隔那你只需要把分隔符换掉栈的逻辑完全一样。还有的变体会要求保留路径中重复的斜杠这种情况下切分方案就不适用了得改用逐字符扫描不过实际面试中很少这么考。我个人做这类题目时有个习惯先不看题解自己把边界用例列出来再写核心逻辑。第71题这个经验我后面一直在用因为大多数翻车都不是算法不会而是边界没想全。先列用例、再写代码、最后对照用例自查这十分钟的流程能帮你省下多次提交错误的时间。如果你也卡在某个用例上过不去拿上面那张速查表逐条跑一遍基本就能定位到问题出在哪一类分支里了。