当前位置：首页 > 力扣 > 力扣388题解析：最长绝对路径（栈+字符串处理优化解法）

力扣388题解析：最长绝对路径（栈+字符串处理优化解法）

5天前

一、题目解读

力扣第388题“最长绝对路径”要求从给定的文本中提取文件系统中目录与文件名的绝对路径，并返回其中最长的路径长度。输入为多行文本，每行由缩进（'\t'）表示层级，末尾以换行符分隔，文件名包含“.”标识。需处理层级关系，计算包含目录与文件名的完整路径长度，并找出最大值。

二、解题思路

采用“栈+字符串解析”的策略，核心思想是通过栈维护当前层级路径长度，利用缩进计算层级变化，动态调整栈结构，避免递归或复杂遍历。关键在于：

1. 通过统计每行开头的缩进数量确定层级；

2. 区分文件与目录，文件计入总长度，目录则更新栈；

3. 利用栈的先进后出特性，确保路径长度随层级变化正确累加。

三、解题步骤

1. 初始化：创建栈存储路径长度，初始为空路径（长度0），记录最大长度maxLen；

2. 逐行解析：

统计缩进数确定当前层级level；

解析文件名（含“.”标记为文件），记录名称长度nameLen；

调整栈至当前层级：若栈内层级多于当前层级，弹出多余元素；

计算当前路径总长度：文件则更新maxLen，目录则添加分隔符长度并入栈；

3. 循环结束：返回maxLen。

四、代码与注释

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

注释说明：代码通过栈动态维护路径长度，利用缩进层级与文件名解析，避免深度遍历，提升效率。