【LeetCode 热题 100】763. 划分字母区间——贪心算法

Problem: 763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

整体思路

这段代码旨在解决一个经典的字符串问题：划分字母区间 (Partition Labels)。问题要求将一个字符串 s 划分为尽可能多的片段，使得同一个字母只会出现在其中的一个片段中。最终返回一个列表，包含这些片段的长度。

该算法采用了一种非常高效的 贪心算法 (Greedy Algorithm)。其核心思想是，对于一个正在构建的片段，我们需要确保这个片段的结束位置必须能够“包含”住其中所有字符的最后一次出现。

算法的逻辑步骤可以分解如下：

1. 预处理：记录每个字符的最后位置

   • 算法的第一步是遍历整个字符串，使用一个哈希表 lastLoc 来记录下每个字符在字符串中最后一次出现的索引。
   • 目的：这个预处理步骤是贪心策略的基础。它使得我们在后续的遍历中，能够以 O(1) 的时间复杂度快速查询到任何一个字符的“最远边界”。

2. 贪心遍历与划分

   • 算法接着对字符串进行第二次、也是主要的遍历。在这次遍历中，它使用两个关键变量来确定每个片段的边界：
     • start：记录当前正在构建的片段的起始索引。
     • maxRight：记录当前片段必须延伸到的最远右边界。
   • 遍历过程：
     a. 当 for 循环的指针 i 在字符串上移动时，我们考虑当前字符 s[i]。
     b. 我们从 lastLoc 哈希表中查出 s[i] 的最后出现位置。
     c. 然后，我们贪心地更新 maxRight，使其等于 maxRight 的当前值和 s[i] 最后出现位置中的较大者。maxRight 的含义是：为了满足条件，当前片段至少要延伸到这个索引才能包含所有已扫描过的字符。
     d. 找到划分点：最关键的一步是判断 if (i == maxRight)。当我们的遍历指针 i 恰好到达了我们所维护的最远边界 maxRight 时，这意味着一个有效的片段已经形成。因为从 start 到 i 的所有字符，它们最后一次出现的位置都小于或等于 i。我们找到了一个最短的、满足条件的有效片段。
   • 记录与重置：
     • 一旦找到划分点，就计算当前片段的长度 maxRight - start + 1，并将其添加到结果列表 ans 中。
     • 然后，将下一个片段的起始位置 start 更新为 maxRight + 1。

3. 返回结果：

   • 当遍历完整个字符串后，ans 列表中就包含了所有划分片段的长度。

完整代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    /**
     * 将字符串划分为尽可能多的片段，使得同一个字母只会出现在一个片段中。
     * @param s 输入的字符串
     * @return 一个包含各片段长度的列表
     */
    public List<Integer> partitionLabels(String s) {
        // ans: 用于动态存储最终各个分区的长度。
        List<Integer> ans = new ArrayList<>();
        // lastLoc: 用于预先存储每个字符在字符串中最后一次出现的位置。
        Map<Character, Integer> lastLoc = new HashMap<>();
        char[] sc = s.toCharArray();
        
        // 步骤 1: 预处理，遍历字符串，填充 lastLoc 哈希表。
        for (int i = 0; i < sc.length; i++) {
            char c = sc[i];
            lastLoc.put(c, i);
        }
        
        // start: 当前正在构建的分区的起始索引。
        int start = 0;
        // maxRight: 当前分区必须延伸到的最远右边界。
        int maxRight = 0;
        
        // 步骤 2: 贪心遍历，寻找并划分分区。
        for (int i = 0; i < sc.length; i++) {
            // 对于当前遍历到的字符 sc[i]，我们需要确保我们的分区能包含它的最后一次出现。
            // 因此，贪心地更新 maxRight，使其成为当前分区内所有字符的“最后出现位置”中的最大值。
            maxRight = Math.max(maxRight, lastLoc.get(sc[i]));
            
            // 关键的判断：如果当前遍历的索引 i 恰好等于我们确定的最远边界 maxRight，
            // 这说明从 start 到 i 的所有字符，其最后一次出现的位置都在这个区间内。
            // 因此，一个有效的、最短的片段已经形成。
            if (i == maxRight) {
                // 计算当前分区的长度并添加到结果列表中。
                ans.add(maxRight - start + 1);
                // 更新下一个分区的起始位置。
                start = maxRight + 1;
            }
        }
        return ans;
    }
}

时空复杂度

时间复杂度：O(N)

1. 预处理：第一个 for 循环遍历整个字符串一次，以填充 lastLoc 哈希表。如果字符串长度为 N，这部分的时间复杂度是 O(N)，因为 HashMap.put 的平均时间复杂度是 O(1)。
2. 贪心遍历：第二个 for 循环也遍历整个字符串一次。在循环内部，lastLoc.get 和 Math.max 都是 O(1) 的操作。因此，这部分的时间复杂度也是 O(N)。

综合分析：
算法的总时间复杂度是两个独立的线性扫描的和：O(N) + O(N) = O(N)。

空间复杂度：O(k) 或 O(1)

1. 主要存储开销：
   • Map<Character, Integer> lastLoc：这是主要的额外辅助空间。它存储了字符串中所有唯一字符及其最后位置。如果字符串中唯一字符的数量为 k，则其空间复杂度为 O(k)。
   • char[] sc = s.toCharArray(): 这个操作创建了字符串的一个副本，占用了 O(N) 的空间。这在分析中可以提及，但通常核心算法的空间复杂度关注的是 lastLoc。
   • List<Integer> ans: 这是输出结果，其空间不计入额外辅助空间复杂度。
2. 分析：
   • k 的值取决于字符集的大小。对于只包含小写英文字母的字符串，k 的最大值是 26。对于ASCII字符集，k 的最大值是 128 或 256。
   • 由于字符集的大小通常被视为一个固定的常数，因此 k 也是一个常数。

综合分析：
算法的额外辅助空间主要由 lastLoc 哈希表决定。其空间复杂度为 O(k)，其中 k 是字符集中字符的数量。因为 k 是一个常数，所以空间复杂度也可以表述为 O(1)。