企业官网建设流程全解析

LeetCode 71这道简化路径，我最近刷了好几遍。题目看着不起眼，样例也友好，但真要动手写的时候，你会发现到处都是坑：split 的边界行为、空栈遇到 ".." 怎么办、最终输出顺序是不是反了……每一处都可能让你在提交的时候碰一鼻子灰。

这道题考的不是什么高深的算法，而是两样面试最看重的素质：对基础数据结构的掌握程度，以及处理边界情况的缜密程度。如果你正在准备算法面试，或者想把栈相关的应用场景吃透，这道题值得拿出来认真拆解一遍。

下面我按自己刷题时的思路，从题目解读、为什么用栈、代码实现、空间优化到真实业务场景，一步步讲清楚。

1. 先把题目读懂：它到底在解决什么问题

1.1 题目还原与典型样例

题面很简单：给定一个字符串path，表示 Unix 风格的文件绝对路径，需要将它转换成规范路径。题目保证path非空，并且一定以/开头。

规范路径的定义有几个硬性要求：

• 必须以/开头。
• 两个目录名之间只能有一个/。
• 路径末尾不能有/，除非它就是根目录/。
• 路径中不能出现.和..这种特殊记号，因为它们分别代表“当前目录”和“上一级目录”，需要被正确处理。

光看文字不够直观，看几个典型样例：

第二个样例值得多说一句。/../在很多人直觉里应该报错，但在 Unix 文件系统中，根目录的上一级仍然是根目录，所以..在根目录处会被忽略。这道题完全遵循这套真实语义。

1.2 潜台词：规范化的三条核心规则

把题目翻译成可执行的规则，其实就三条：

• 规则一：连续的/视作一个/。比如/home//foo等价于/home/foo。
• 规则二：.表示当前目录，直接忽略。它不改变当前位置，也没有任何副作用。
• 规则三：..表示回到上一级目录。如果当前已经在根目录，则忽略；否则需要把当前目录层级“撤销”掉。

这三条规则合在一起，本质上就是在做一件事：把路径串里的冗余信息全部清洗掉，只保留“从根目录到最终位置”的唯一描述。

1.3 这类问题在真实场景里意味着什么

可能有人觉得路径简化只是刷题用，其实不然。浏览器解析 URL 时要处理./和../；构建工具解析模块导入路径时要折叠冗余层级；文件系统 API 做路径规范化时也遵循同样的逻辑。说白了，你把这道题弄明白，就理解了现代软件里路径处理的基本盘。

还有一点私心建议：这道题非常适合作为“栈”专题的入门题。它的难度适中，逻辑清晰，不像有些栈题那样上来就是单调栈劝退。做透了它，后面再遇到“目录层级”“括号匹配”这类问题，思路会顺很多。

2. 为什么要用栈：目录层级天然匹配 LIFO

2.1 目录层级就是一摞盘子

很多人看到这题第一反应是：直接字符串替换不行吗？把/./换成空，把/../连同前面的目录一起删掉？能想到这一步说明有感觉，但字符串替换在遇到嵌套和边界情况时会非常混乱，比如/a/../../b，你需要反复扫描才能处理干净。

更干净的思路是：把目录层级看成“一摞盘子”。你从根目录出发：

• 遇到一个普通目录名，比如a，就是往这摞盘子上放一个新盘子。
• 遇到..，就是把最上面的盘子拿走，回到上一层。
• 遇到.或空字符串，什么都不做。

最终盘子里剩下的，从下往上看，就是简化后的路径目录序列。这个“最上面”一直在变，而“最近放入的目录”最先被移除，这恰恰是栈（Stack）的语义：后进先出（LIFO）。

拿综合样例走一遍流程：

输入/a/./b/../../c/，按/切分后得到以下部分：空串、a、.、b、..、..、c。

• 空串：跳过。
• a：入栈，栈内[a]。
• .：跳过。
• b：入栈，栈内[a, b]。
• ..：弹栈，移除b，栈内[a]。
• ..：弹栈，移除a，栈变为空。
• c：入栈，栈内[c]。

最后栈里只剩一个c，拼接后输出/c。全流程跟前面表格里的预期完全一致。

这就是栈解法为什么是标准答案的原因：它用数据结构天然模拟了“进入目录”和“回到上一级”这两种互逆操作，不需要你手动维护复杂的字符串状态。

2.2 为什么队列和递归都不是好选择

既然提到了选型，顺手说说为什么不用别的结构。

• 队列（Queue）：队列是先进先出（FIFO），从头到尾依次处理。如果用它存目录序列，遇到..时你需要从队尾回退，但队尾在队列里恰恰是最后才应该被访问的位置。强行回退要么破坏队列语义，要么需要额外数据结构辅助，得不偿失。
• 递归（Recursion）：递归本质是在用系统调用栈做回溯，理论上可行，但路径深度可能很大，递归层数一旦上去就有爆栈风险。而且在迭代就能解决的问题上强行递归，代码可读性和健壮性都会打折扣。
• 字符串原地修改：逻辑上绕，频繁拼接和删除会带来不必要的性能损耗，还容易在嵌套回退时出逻辑漏洞。

栈是唯一同时满足“语义匹配”“实现简单”“时空复杂度可控”的选择。

2.3 从“有效括号”看这类抵消题的共性

如果你刷过有效括号那类题，会发现它们跟这题有很强的相似感。括号匹配是(和)之间的配对抵消，而这里的“抵消”发生在“目录名”和..之间。更抽象一层，它们都属于后出现的操作符作用于先出现的单元：..要抵消的是它左侧最近的目录，就像右括号要匹配左括号一样。

这种共性特别重要。一道题一道题地硬刷，效率很低；但当你意识到“哦，这类题目都是栈的抵消和回溯”，很多题就通了。刷题的价值不在于背题，而在于建立这种模式识别的能力。

3. 栈解法实现与关键细节：一份能跑通的 Java 代码

3.1 可以直接复用的 Java 实现

先给出一份完整、简洁的实现，然后用运行结果验证正确性：

class Solution { public String simplifyPath(String path) { // 按 / 切分，连续斜杠和首尾斜杠都会产生空字符串 String[] dirs = path.split("/"); Deque<String> stack = new ArrayDeque<>(); for (String dir : dirs) { // 空字符串代表多余斜杠；"." 代表当前目录 if (dir.isEmpty() || dir.equals(".")) { continue; } // ".." 返回上一级目录 if (dir.equals("..")) { if (!stack.isEmpty()) { stack.pop(); } } else { // 普通目录名入栈 stack.push(dir); } } // 栈空说明最终停留在根目录 if (stack.isEmpty()) { return "/"; } // 从栈底开始拼接，保证顺序正确 StringBuilder sb = new StringBuilder(); while (!stack.isEmpty()) { sb.append('/').append(stack.pollLast()); } return sb.toString(); } }

用刚才那几个样例跑一遍，输出全部正确。这份代码基本是这道题在 Java 语境下的标准写法了，记忆成本很低。

3.2 逐行拆解：每个关键步骤背后的为什么

第一步：split("/") 是这道题第一个隐藏考点。

path.split("/")会把字符串按斜杠切分，但它有几个行为需要注意：

• 字符串/a/b切分后是["", "a", "b"]，开头会产生一个空串。
• 字符串/a//b切分后是["", "a", "", "b"]，连续斜杠会产生中间空串。
• 字符串/a/切分后是["", "a"]，结尾的空串会被默认丢弃。

所以代码里用dir.isEmpty()显式跳过空串，不是多余动作，而是在清理 split 带来的“斜杠残留”。我见过不少人在这里不处理空串，然后发现输出里平白多出好几个/。

第二步：遇到..时，先判断栈是否为空。

这是第二个高频翻车点。如果当前已经在根目录，栈是空的，此时..不能做任何操作。比如路径/..，处理流程是：遇到空串跳过，遇到..发现栈为空，直接忽略，最后返回/。如果这里不判空直接pop()，运行时会直接抛异常。

第三步：拼接结果时从栈底开始取。

Java 的Deque接口里，push是往头部放元素，pop是从头部取元素。也就是说，如果依次 push 了a、b、c，栈内从头到尾视图是[c, b, a]。但我们要输出的顺序是a/b/c，从根目录到深层目录。所以不能简单地从栈顶遍历，而要借助pollLast()从栈底逐个取出，或者用descendingIterator。这是这题里最容易“逻辑对但输出反了”的地方。

反过来，如果不想取栈底，也可以先把栈元素倒入辅助栈再拼接，但那样多一次 O(n) 的遍历，没必要。

3.3 为什么用 ArrayDeque 而不是 Stack

很多初学者会直接用 Java 的Stack类，这也能跑通，但从工程和面试的角度，我更推荐Deque接口配合ArrayDeque实现。

• Stack继承自Vector，方法上带着同步锁。在单线程算法题里，这种线程安全是不必要的开销。
• ArrayDeque作为双端队列实现，push/pop/peek都是 O(1)，没有同步开销，支持扩容，底层是数组，缓存友好。
• 面试时如果你能说出“Stack 是遗留类，我更推荐 Deque”，会让面试官觉得你不只刷过题，还懂 Java 集合框架的演进。

顺便补充一个细节：ArrayDeque不允许放入null，但本题的目录名经过 split 后不会产生null，所以可以放心使用。

3.4 关于 split("/") 的三个坑

第一，不要以为 split 会帮你把连续斜杠清理干净。/a//b得到["", "a", "", "b"]，空串必须你在循环里主动跳过。

第二，尾部的空串默认被丢弃。也就是说/a/和/a的切分结果在“尾部空串”这一点上是一样的，这个默认行为不会给你添乱，但你要知道它存在，否则看到["", "a"]时可能疑惑为什么尾部空串不见了。

第三，有人会用split("/+")来正则匹配连续斜杠，确实能减少空串个数，但开头斜杠导致的前导空串依然存在，而且正则表达式比固定分隔符慢。在 LeetCode 这种量级的输入上差别不大，但没必要为了少写一个isEmpty()判断引入正则，split("/") + isEmpty()是更清晰通用的组合。

4. 进阶解法：逆序扫描，把额外空间压到 O(1)

4.1 思路来源：从答案的构造反推

栈解法是正着扫描路径，用入栈、出栈模拟目录切换。空间复杂度 O(n)，因为最坏情况下栈要存下所有目录名。

但如果换个角度：从路径末尾向前扫描，会发生什么？

我们知道，..会抵消它左侧（更靠前）的一个普通目录。从右往左看这个抵消关系同样成立：遇到一个..，就相当于“欠”一个普通目录的抵消名额；之后遇到普通目录时，先看看有没有未抵消的..，有就抵消掉，没有才保留。

这样就不需要显式栈了，只需要一个计数器skip记录“还没被抵消的 .. 数量”，加上一个结果列表保存保留下来的目录名。由于是从右往左收集，结果列表的顺序是“深层目录在前、浅层目录在后”，最后再反转一下，拼接即可。

额外空间上，除了保存最终答案的列表，我们只需要一个整数skip，属于 O(1) 辅助空间。如果题目要求你写出“不用栈”的解法，这就是加分答案。

4.2 逆序扫描的代码实现

class Solution { public String simplifyPath(String path) { String[] dirs = path.split("/"); int skip = 0; List<String> res = new ArrayList<>(); for (int i = dirs.length - 1; i >= 0; i--) { String dir = dirs[i]; if (dir.equals("..")) { skip++; // 记下一次待抵消 } else if (dir.isEmpty() || dir.equals(".")) { continue; // 空串和当前目录直接跳过 } else { if (skip > 0) { skip--; // 抵消一次 .. } else { res.add(dir); // 保留这个目录 } } } if (res.isEmpty()) { return "/"; } Collections.reverse(res); // 恢复根目录到深层的顺序 StringBuilder sb = new StringBuilder(); for (String dir : res) { sb.append('/').append(dir); } return sb.toString(); } }

用/a/./b/../../c/验证一下：

split("/")得到["", "a", ".", "b", "..", "..", "c"]，从右向左处理：

• c：skip=0，保留，res=[c]。
• ..：skip=1。
• ..：skip=2。
• b：skip>0，skip=1。
• .：跳过。
• a：skip>0，skip=0。
• 空串：跳过。

最终 res=[c]，反转后还是 [c]，输出/c。正确。

再试/a/b/../c：

从右向左：c保留，res=[c]；..skip=1；bskip=0；a保留，res=[c, a]。反转后为[a, c]，拼接成/a/c。正确，因为/a/b/../c等价于/a/c。

4.3 两种解法全方位对比

我的建议是：先写栈解法，保证正确性和稳定性；如果面试官追问“能不能省空间”，再补充逆序计数解法。这比一上来就写逆序解法更稳妥，毕竟思路越绕越容易出错。

5. 边界情况与易错点：一次全梳理

5.1 边界情况速查表

最后一个/...很容易被忽略。题目规则只把.和..当特殊记号，三个点的字符串是合法的目录名，必须正常入栈。如果代码里判断写成了if (dir.contains(".."))就会翻车，这里应该用equals而不是contains。

5.2 面试现场最容易翻车的三个点

第一，空栈弹栈。路径为/..时，如果直接stack.pop()会抛异常。正确做法是if (!stack.isEmpty()) stack.pop()。

第二，拼接顺序错乱。栈的解法和队列不一样，直接用迭代器从头遍历会得到反向结果。正确做法是从栈底向栈顶遍历拼接，或者全部弹出后再反转。第三，漏掉根目录特判。如果最终栈为空，要返回/，而不是空字符串。这个特判虽然简单，但在代码写到一半思维跳跃的时候很容易丢掉。

5.3 时间复杂度与空间复杂度再确认

• 时间复杂度：O(n)。split扫描一次字符串是 O(n)，栈或计数器处理每个元素是 O(1)，拼接结果是 O(n)，总体线性。
• 空间复杂度：栈解法是 O(n)，逆序解法除了最终答案外是 O(1)。注意split生成的字符串数组本身也占 O(n) 空间，所以如果严格按“包含输入输出的全部内存占用”来算，逆序解法整体还是 O(n)；但面试桌上通常只讨论算法的辅助空间，这时候逆序解法确实可以理直气壮地说 O(1)。

6. 从 LeetCode 到真实业务：路径处理的实战扩展

6.1 URL 规范化与浏览器行为

你在浏览器地址栏输入https://example.com/a/../b/，浏览器解析时同样要处理..回退。URL 规范化的核心规则和这道题如出一辙：把.忽略，把..视作回到上一级目录。区别在于 URL 里还有协议、域名、查询参数、锚点等更多结构，但路径部分的处理逻辑完全可以复用本题思路。

如果你负责维护一个爬虫或者路由工具，遇到 URL 去重时，手动解析路径中的..是家常便饭。用这道题的栈解法稍作封装，就能写一个简易的 path.normalize 工具。

6.2 如果遇到 Windows 路径

Windows 路径用反斜杠\，还有盘符，逻辑比 Unix 路径复杂一些。比如C:\Users\foo\..\bar，简化后是C:\Users\bar。

• 分隔符从/换成\，split 时要注意反斜杠在正则里需要转义，写成path.split("\\\\")。
• 盘符是第一个“目录名”，回退时如果只剩盘符，依然不能继续回退。
• 有些 Windows 路径还涉及 UNC 路径（以\\开头），处理逻辑更复杂。

不过底层思路完全一样，栈或者计数器照用不误。真正理解了一道题，换层皮也能做。

6.3 工程中的成熟方案对比

在实际的 Java 工程里，我不会手写这套逻辑，而是直接用标准库。java.nio.file.Path提供了normalize()方法，内部实现就是处理.和..，而且考虑到了操作系统差异。写业务代码时优先用标准库，维护成本低、正确性有保障。

但算法面试为什么要手写？因为面试官考的是你的抽象能力和边界敏感度，而不是你会不会调库。两个层面你都准备好了，才能在面试和工程之间做到游刃有余。

我自己做这道题最大的体会是：写代码之前先画出栈的状态变化图。把a入栈、..弹栈、最终拼接的过程在纸上过一遍，比直接撸代码管用得多。画完一遍你就会发现，这道题根本不是考查记忆能力，而是考查你能不能“看见”数据的流动过程。动手之前把流程理顺，思路通了，代码自然不会跑偏。