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

8小时前力扣题解27

一、问题背景

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

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

表示目录结构：

dir/
    subdir1/
    subdir2/
        file.ext

二、核心思路

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

层级计算：通过\t数量确定当前项所处层级
名称提取：记录名称长度并检测文件扩展名
栈调整：保持栈内只保留当前路径的祖先节点
长度计算：文件则更新最大值，目录则入栈备用

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

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;
    }
};