栈结构在文件路径问题中的妙用：力扣388题最长绝对路径详解

一、问题背景

力扣388题要求我们计算文件系统中文件的最长绝对路径长度。输入字符串使用\t表示层级关系，\n分隔不同文件/目录。例如：

"dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"

表示目录结构：

dir/
    subdir1/
    subdir2/
        file.ext

二、核心思路

使用栈结构维护当前路径的累计长度，通过以下4个关键步骤处理每个文件/目录：

1. 层级计算：通过\t数量确定当前项所处层级

2. 名称提取：记录名称长度并检测文件扩展名

3. 栈调整：保持栈内只保留当前路径的祖先节点

4. 长度计算：文件则更新最大值，目录则入栈备用

三、完整实现代码（带注释）

class Solution {
public:
    int lengthLongestPath(string input) {
        stack<int> pathLengths; // 存储各级路径长度
        pathLengths.push(0);    // 初始空路径
        int maxLen = 0;         // 记录最大长度
        size_t i = 0;
        
        while (i < input.size()) {
            // 1. 计算当前层级
            int level = 0;
            while (i < input.size() && input[i] == '\t') {
                ++level;
                ++i;
            }
            
            // 2. 提取当前文件/目录名
            bool isFile = false;
            int nameLen = 0;
            while (i < input.size() && input[i] != '\n') {
                if (input[i] == '.') isFile = true;
                ++nameLen;
                ++i;
            }
            
            // 3. 调整栈到当前层级
            while (level + 1 < pathLengths.size()) {
                pathLengths.pop();
            }
            
            // 4. 计算当前路径总长度
            int currentLen = pathLengths.top() + nameLen;
            if (isFile) {
                maxLen = max(maxLen, currentLen);
            } else {
                currentLen += 1; // 添加路径分隔符'/'
                pathLengths.push(currentLen);
            }
            
            ++i; // 跳过换行符
        }
        
        return maxLen;
    }
};

四、关键点解析

1. 栈的初始化：初始压入0处理根目录情况

2. 层级控制：level+1 < stack.size()确保栈深与当前层级匹配

3. 路径分隔符：目录需要额外+1计入/的长度

4. 时间复杂度：O(n)单次遍历，每个字符只处理一次

五、实际案例演示

以输入"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"为例：

1. 处理dir时栈变为[0,4]

2. 处理subdir1时栈变为[0,4,8]

3. 遇到file1.ext时计算长度12

4. 最终得到最长路径长度32

六、总结

该解法巧妙利用栈结构：

• 天然处理目录的嵌套关系

• 通过出栈操作实现目录回溯

• 空间复杂度O(d)（d为最大深度）

• 可扩展处理更复杂的路径规则