Partition Lables

763. 划分字母区间

分析

记录每个字母的最远出现位置：
- 遍历字符串，记录每个字符最后一次出现的索引，存储在哈希表 hash 中
划分片段：
- 使用变量 start 表示当前片段的起始位置，end 表示当前片段中字符的最远位置
- 遍历字符串时，动态更新当前片段的最远位置 end
- 当当前索引 i 等于 end 时，表示当前片段结束，将片段长度加入结果数组 res
更新起点：
- 划分一个片段后，将 start 更新为 i + 1，准备划分下一个片段

时间复杂度

记录最远位置: O(n)，需要遍历一次字符串记录字符的最远位置
划分片段: O(n)，第二次遍历字符串进行片段划分

总体时间复杂度为 O(n)

空间复杂度

哈希表 hash 的空间复杂度为 O(k)，其中 k 是字符集大小（对于英文字母，k < 26）
结果数组 res 需要额外存储片段长度，空间复杂度为 O(p)，其中 p 是片段数量

总体空间复杂度为 O(k + p)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution
{
public:
    vector<int> partitionLabels(string s)
    {
        // 记录每个字符的最远出现位置
        std::unordered_map<char, int> hash;
        for (int i = 0; i < s.size(); ++i)
            hash[s[i]] = i;

        std::vector<int> res; // 存储结果
        int start = 0, end = 0;

        for (int i = 0; i < s.size(); ++i)
        {
            // 更新当前片段的最远边界
            end = std::max(end, hash[s[i]]);

            // 当前片段结束
            if (i == end)
            {
                res.push_back(end - start + 1); // 保存片段长度
                start = end = i + 1;           // 更新起点，准备下一个片段
            }
        }

        return res;
    }
};