文件的最长绝对路径 图解题解

这道题到底在问什么

输入

dir 换行 制表符 subdir1 换行 制表符 subdir2 换行 制表符制表符 file.ext

输出

20

输入

本节演示（含两个文件的目录树）

输出

32

最优解：一步一步想明白

1. 3记牢「栈存每层累计长、栈高等于深度、弹栈对齐父层、加一是斜杠、目录入栈文件刷答案」，下面每一帧都在套它。
2. 4先把整段文本按换行符拆成 7 行摆在上方，前面的「·」点表示这一行的缩进深度（制表符个数）。栈一开始是空的，我们从第一行开始，逐行往栈里维护「每层累计路径长」。
3. 5扫到第 0 行「dir」。它前面有 0 个制表符，所以深度是 0；名字本身 3 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
4. 6栈现在是空的，说明「dir」就在根目录下，没有父层，前面也不用加斜杠。它的累计长度就等于名字本身 3。
5. 7累计 = 名字 3 = 3。「dir」是目录，把这个累计 3 压进栈，它就成了下一层更深目录的父层。继续看下一行。
6. 8扫到第 1 行「subdir1」。它前面有 1 个制表符，所以深度是 1；名字本身 7 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
7. 9这一行深度 1，栈高正好是 1，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「dir」，累计 3。
8. 10累计 = 名字 7 + 父层 3 + 斜杠 1 = 11。「subdir1」是目录，把这个累计 11 压进栈，它就成了下一层更深目录的父层。继续看下一行。
9. 11扫到第 2 行「file1.ext」。它前面有 2 个制表符，所以深度是 2；名字本身 9 个字符。名字里带点号，它是个文件。先看看栈要不要弹。
10. 12这一行深度 2，栈高正好是 2，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「subdir1」，累计 11。
11. 13「file1.ext」是文件，它对应一条完整绝对路径，候选路径长 = 名字 9 + 父层 11 + 斜杠 1 = 21。21 比旧答案 0 大，刷新答案为 21。文件不入栈，继续往下扫。
12. 14扫到第 3 行「subsubdir1」。它前面有 2 个制表符，所以深度是 2；名字本身 10 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
13. 15这一行深度 2，栈高正好是 2，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「subdir1」，累计 11。
14. 16累计 = 名字 10 + 父层 11 + 斜杠 1 = 22。「subsubdir1」是目录，把这个累计 22 压进栈，它就成了下一层更深目录的父层。继续看下一行。
15. 17扫到第 4 行「subdir2」。它前面有 1 个制表符，所以深度是 1；名字本身 7 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
16. 18这一行深度 1，可栈里还压着更深的层。规则是「栈高 > 深度就弹」，于是连弹 2 个，把栈高对齐成 1。现在栈顶就是它的父层「dir」，累计 3。
17. 19累计 = 名字 7 + 父层 3 + 斜杠 1 = 11。「subdir2」是目录，把这个累计 11 压进栈，它就成了下一层更深目录的父层。继续看下一行。
18. 20扫到第 5 行「subsubdir2」。它前面有 2 个制表符，所以深度是 2；名字本身 10 个字符。名字里没有点号，它是个目录。先看看栈要不要弹。
19. 21这一行深度 2，栈高正好是 2，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「subdir2」，累计 11。
20. 22累计 = 名字 10 + 父层 11 + 斜杠 1 = 22。「subsubdir2」是目录，把这个累计 22 压进栈，它就成了下一层更深目录的父层。继续看下一行。
21. 23扫到第 6 行「file2.ext」。它前面有 3 个制表符，所以深度是 3；名字本身 9 个字符。名字里带点号，它是个文件。先看看栈要不要弹。
22. 24这一行深度 3，栈高正好是 3，不满足「栈高 > 深度」，所以一个都不弹。栈顶的父层是「subsubdir2」，累计 22。
23. 25「file2.ext」是文件，它对应一条完整绝对路径，候选路径长 = 名字 9 + 父层 22 + 斜杠 1 = 32。32 比旧答案 21 大，刷新答案为 32。文件不入栈，继续往下扫。
24. 26全部扫完。两个文件里，file1.ext 那条是 21，file2.ext 那条最长，正是 dir/subdir2/subsubdir2/file2.ext，长度 3+1+7+1+10+1+9 = 32。栈始终只维护「当前这条路径」上的每层累计，一遍扫描就锁定了答案 32。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int lengthLongestPath(string input) {
        int i = 0, n = input.size();
        int ans = 0;
        stack<int> stk;
        while (i < n) {
            int ident = 0;
            for (; input[i] == '\t'; ++i) {
                ++ident;
            }

            int cur = 0;
            bool isFile = false;
            for (; i < n && input[i] != '\n'; ++i) {
                ++cur;
                if (input[i] == '.') {
                    isFile = true;
                }
            }
            ++i;

            // popd
            while (!stk.empty() && stk.size() > ident) {
                stk.pop();
            }

            if (stk.size() > 0) {
                cur += stk.top() + 1;
            }

            // pushd
            if (!isFile) {
                stk.push(cur);
                continue;
            }

            ans = max(ans, cur);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int lengthLongestPath(String input) {
        int i = 0;
        int n = input.length();
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        while (i < n) {
            int ident = 0;
            for (; input.charAt(i) == '\t'; i++) {
                ident++;
            }

            int cur = 0;
            boolean isFile = false;
            for (; i < n && input.charAt(i) != '\n'; i++) {
                cur++;
                if (input.charAt(i) == '.') {
                    isFile = true;
                }
            }
            i++;

            // popd
            while (!stack.isEmpty() && stack.size() > ident) {
                stack.pop();
            }

            if (stack.size() > 0) {
                cur += stack.peek() + 1;
            }

            // pushd
            if (!isFile) {
                stack.push(cur);
                continue;
            }

            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

复杂度

面试官可能追问