题目描述
思路解析动画文字版
记牢「栈存每层累计长、栈高等于深度、弹栈对齐父层、加一是斜杠、目录入栈文件刷答案」，下面每一帧都在套它。
总览 · 把目录树排成 7 行：先把整段文本按换行符拆成 7 行摆在上方，前面的「·」点表示这一行的缩进深度（制表符个数）。栈一开始是空的，我们从第一行开始，逐行往栈里维护「每层累计路径长」。
读第 0 行 · dir：扫到第 0 行「dir」。它前面有 0 个制表符，所以深度是 0；名字本身 3 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
弹栈对齐 · 深度 0：栈现在是空的，说明「dir」就在根目录下，没有父层，前面也不用加斜杠。它的累计长度就等于名字本身 3。
目录入栈 · 累计 3：累计 = 名字 3 = 3。「dir」是目录，把这个累计 3 压进栈，它就成了下一层更深目录的父层。继续看下一行。
读第 1 行 · subdir1：扫到第 1 行「subdir1」。它前面有 1 个制表符，所以深度是 1；名字本身 7 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
弹栈对齐 · 深度 1：这一行深度 1，栈高正好是 1，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「dir」，累计 3。
目录入栈 · 累计 11：累计 = 名字 7 + 父层 3 + 斜杠 1 = 11。「subdir1」是目录，把这个累计 11 压进栈，它就成了下一层更深目录的父层。继续看下一行。
读第 2 行 · file1.ext：扫到第 2 行「file1.ext」。它前面有 2 个制表符，所以深度是 2；名字本身 9 个字符。名字里带点号，它是个文件。先看看栈要不要弹。
弹栈对齐 · 深度 2：这一行深度 2，栈高正好是 2，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「subdir1」，累计 11。
文件结算 · 候选 21：「file1.ext」是文件，它对应一条完整绝对路径，候选路径长 = 名字 9 + 父层 11 + 斜杠 1 = 21。21 比旧答案 0 大，刷新答案为 21。文件不入栈，继续往下扫。
读第 3 行 · subsubdir1：扫到第 3 行「subsubdir1」。它前面有 2 个制表符，所以深度是 2；名字本身 10 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
弹栈对齐 · 深度 2：这一行深度 2，栈高正好是 2，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「subdir1」，累计 11。
目录入栈 · 累计 22：累计 = 名字 10 + 父层 11 + 斜杠 1 = 22。「subsubdir1」是目录，把这个累计 22 压进栈，它就成了下一层更深目录的父层。继续看下一行。
读第 4 行 · subdir2：扫到第 4 行「subdir2」。它前面有 1 个制表符，所以深度是 1；名字本身 7 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
弹栈对齐 · 深度 1：这一行深度 1，可栈里还压着更深的层。规则是「栈高 > 深度就弹」，于是连弹 2 个，把栈高对齐成 1。现在栈顶就是它的父层「dir」，累计 3。
目录入栈 · 累计 11：累计 = 名字 7 + 父层 3 + 斜杠 1 = 11。「subdir2」是目录，把这个累计 11 压进栈，它就成了下一层更深目录的父层。继续看下一行。
读第 5 行 · subsubdir2：扫到第 5 行「subsubdir2」。它前面有 2 个制表符，所以深度是 2；名字本身 10 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
弹栈对齐 · 深度 2：这一行深度 2，栈高正好是 2，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「subdir2」，累计 11。
目录入栈 · 累计 22：累计 = 名字 10 + 父层 11 + 斜杠 1 = 22。「subsubdir2」是目录，把这个累计 22 压进栈，它就成了下一层更深目录的父层。继续看下一行。
读第 6 行 · file2.ext：扫到第 6 行「file2.ext」。它前面有 3 个制表符，所以深度是 3；名字本身 9 个字符。名字里带点号，它是个文件。先看看栈要不要弹。
弹栈对齐 · 深度 3：这一行深度 3，栈高正好是 3，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「subsubdir2」，累计 22。
文件结算 · 候选 32：「file2.ext」是文件，它对应一条完整绝对路径，候选路径长 = 名字 9 + 父层 22 + 斜杠 1 = 32。32 比旧答案 21 大，刷新答案为 32。文件不入栈，继续往下扫。
收束 · 答案 32：全部扫完。两个文件里，file1.ext 那条是 21，file2.ext 那条最长，正是 dir/subdir2/subsubdir2/file2.ext，长度 3+1+7+1+10+1+9 = 32。栈始终只维护「当前这条路径」上的每层累计，一遍扫描就锁定了答案 32。
边界先想清：没有文件返回 0、根下文件就是名字长、同层多文件取最长。
面试重点：栈复用公共前缀避免重复拼接；要返回路径就顺带存名字。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def lengthLongestPath(self, input: str) -> int: i, n = 0, len(input) ans = 0 stk = [] while i < n: ident = 0 while input[i] == '\t': ident += 1 i += 1 cur, isFile = 0, False while i < n and input[i] != '\n': cur += 1 if input[i] == '.': isFile = True i += 1 i += 1 # popd while len(stk) > 0 and len(stk) > ident: stk.pop() if len(stk) > 0: cur += stk[-1] + 1 # pushd if not isFile: stk.append(cur) continue ans = max(ans, cur) return ans复杂度
- 时间：O(n)，n 为字符串长度，每个字符只被扫一次
- 空间：O(d)，d 为最大目录深度，栈最多存一条路径上的各层
易错点
面试追问把动画讲成自己的话
追问为什么用栈，而不是把每条路径都拼成字符串再求长？
追问如果还要返回那条最长路径本身（而不只是长度），怎么改？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符串解码
LeetCode 394 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题