元宝 LeetCode 388. 文件的最长绝对路径 Java实现

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

核心思路

“\\t” 的个数 = 该层深度。核心等式：

当前绝对路径长度 = 父目录累计长度 + 本层名字长度 + 1（分隔符
“/”）
因为遍历是前序的（父一定先于子出现），所以扫到某一行时，它父目录的累计长度必定已经算好并存下来了。

关键细节：

• 目录存起来供孩子复用，且长度含末尾
  “/”
• 文件（名字含
  “.”）不存，只用它更新最大值，且要减去那个多算的
  “/”
• 回退到浅层时不用清理深层数据——下次同深度会直接覆盖

写法一：数组存各深度累计长度（最推荐）

class Solution {
public int lengthLongestPath(String input) {
// sum[d] = 深度 d 的目录，其绝对路径长度（含末尾 ‘/’）
int[] sum = new int[input.length() + 1];
int max = 0;

for (String line : input.split("\\n")) {
int depth = 0;
while (depth < line.length() && line.charAt(depth) == '\\t') depth++; // 数 tab
String name = line.substring(depth);

int parentLen = (depth == 0) ? 0 : sum[depth – 1];
int total = parentLen + name.length() + 1; // +1 是 '/'

if (name.contains(".")) {
max = Math.max(max, total – 1); // 文件无末尾 '/'
} else {
sum[depth] = total;
}
}
return max;
}

}

写法二：栈（回溯时回滚长度）

class Solution {
public int lengthLongestPath(String input) {
Deque stack = new ArrayDeque<>(); // 每层贡献 = name长度 + 1
int cur = 0, max = 0; // cur = 当前目录的绝对路径长度(含’/')

for (String line : input.split("\\n")) {
int depth = 0;
while (line.charAt(depth) == '\\t') depth++;
while (stack.size() > depth) cur -= stack.pop(); // 回退到父层
String name = line.substring(depth);

if (name.contains(".")) {
max = Math.max(max, cur + name.length()); // 直接拼，不加 '/'
} else {
stack.push(name.length() + 1);
cur += name.length() + 1;
}
}
return max;
}

}

两写法本质相同，栈版多一次「回退时减长度」的操作，数组版靠下标直接取父值，更省事。

复杂度

• 时间
  “O(n)”：
  “split” + 每个字符扫一遍（数 tab 和取名字各一次）
• 空间
  “O(n)”：split 产生的字符串数组；辅助数组/栈仅
  “O(最大深度)”

易错点提醒

坑 说明
名字里的空格 如
“dir\\n\\t file.txt”，文件名含空格，长度要照算（该例答案 20）
只有目录没有文件 答案是 0，不要返回目录长度
判断文件用
“contains(”.“)” 题目约定文件名一定带扩展名

“split(”\\n")" 若担心末尾空行可用
“split(”\\n", -1)"，本题输入无此情况

已用 7 组用例验证通过：
“20 / 32 / 0 / 9 / 20(含空格文件名) / 12 / 14”，均与手算路径长度一致。