【贪心算法】LC 763.划分字母区间-育师

文章目录

前言
一、题目
- 1、原题链接
- 2、题目描述
二、个人思路整理
- 1、思路分析
- 2、解题代码
三、知识风暴

前言
本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

763.划分字母区间

2、题目描述

二、个人思路整理

1、思路分析

核心思路：题目要求同一字母最多出现在一个片段中，这意味着：同一个字母的所有出现位置，必须被圈在同一个片段里。因此，一个片段至少要延伸到该片段内所有字符最后一次出现的位置。为了让划分出的片段尽可能多，我们需要让每个片段在满足条件的前提下尽可能短。

具体步骤：

预处理最后出现位置：遍历一次字符串，用一个长度为 26 的数组或哈希表last_pos记录每个小写字母在字符串中最后一次出现的下标。
贪心扩展与切分：
- 维护当前区间的起始索引start = 0和当前必须覆盖到的最远右边界end = 0。
- 再次从左到右遍历字符串：
  - 访问到字符s[i]时，该字符的最后出现位置为last_pos[s[i] - 'a']，当前区间的右边界必须向右扩展：end = max(end, last_pos[s[i] - 'a'])。
  - 当遍历指针i刚好追上end时（即i == end），说明当前区间内的所有字符在后面都不会再出现了，当前片段可以切断。
  - 记录片段长度end - start + 1，并将start更新为end + 1，开始寻找下一个片段。

2、解题代码

classSolution{public:vector<int>partitionLabels(string s){// last[c - 'a'] 记录字符 c 在字符串中最后依次出现的索引位置intlast[26]={0};intn=s.size();// 第一次遍历：统计每个字符在字符串中最后出现的下标for(inti=0;i<n;i++){last[s[i]-'a']=i;}vector<int>result;intstart=0;// 当前切分片段的起始下标intend=0;// 当前片段中所有字符所要求的最远右边界// 第二次遍历：贪心地扩展右边界并在满足条件时进行切分for(inti=0;i<n;i++){// 当前片段必须至少延伸到字符 s[i] 的最后出现位置end=max(end,last[s[i]-'a']);// 当遍历到达当前片段所要求的最远边界时，说明该片段内的所有字符在之后的字符串中都不会再出现，此时可以完成依次切分if(i==end){result.push_back(end-start+1);// 记录当前片段长度start=end+1;// 更新下一个片段的起始位置}}returnresult;}};

复杂度分析
时间复杂度：O ( n ) O(n)O(n)，只需两次遍历字符串，其中n nn为字符串长度。
空间复杂度：O ( 1 ) O(1)O(1)（或O ( ∣ Σ ∣ ) O(\vert{}\Sigma\vert{})O(∣Σ∣)），字符集仅包含 26 个小写字母，占用的辅助数组空间为常数级别。

三、知识风暴

贪心算法（Greedy Algorithm）是本题的核心算法思想。它通过在每一步做出当前看起来最优的选择，期望最终得到全局最优解。对于「划分字母区间」这类具有最优子结构性质的问题，贪心策略往往能以O ( n ) O(n)O(n)的复杂度高效求解。

算法核心思想：

局部最优推导全局最优：每一步都让当前片段「尽可能短」，同时保证片段内所有字符的最后出现位置都被覆盖。本题中，维护当前片段必须覆盖到的最远右边界end，当遍历指针追上end时即可切分，从而保证片段数量最多。
无需回溯：贪心算法不回溯、不枚举所有可能的切分方案，只关注当前片段内字符的最远出现位置，因此时间复杂度仅为O ( n ) O(n)O(n)。
与动态规划的区别：动态规划需要枚举所有可能的切分点并逐一比较；而贪心只维护「当前片段的起始位置」和「必须覆盖的最远右边界」两个变量，空间复杂度降为O ( 1 ) O(1)O(1)。

常见对比：贪心 vs 动态规划

贪心算法：时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( 1 ) O(1)O(1)。适合每一步的局部最优能直接推导全局最优的场景，代码简洁高效。
动态规划：时间复杂度O ( n 2 ) O(n^2)O(n2)，空间复杂度O ( n ) O(n)O(n)。适合需要枚举所有子问题、且局部最优不能直接决定全局最优的场景，通用性更强但开销更大。
共同点：两者都依赖「最优子结构」性质。区别在于贪心只保留一个当前最优状态，而动态规划需要维护一张状态表。

贪心算法的设计思想：

核心思想：在遍历过程中，始终维护「当前片段内所有字符的最后出现位置」所要求的最远右边界。当遍历指针到达该边界时，说明当前片段内的所有字符在后续字符串中都不会再出现，此时可以安全切分。
与本题的联系：划分字母区间问题保证每个字母至少出现一次，因此贪心策略不会出现「无法切分」的失败情况。我们只需在遍历过程中不断扩展右边界，即可得到尽可能多的片段。
注意事项：贪心算法并不总是正确，需要先证明「局部最优能推出全局最优」。本题中，让每个片段尽可能短不会比让片段更长更差，因此贪心成立。

使用要点：

边界变量：start记录当前片段的起始下标，end记录当前片段内所有字符所要求的最远右边界。
更新时机：访问到字符s[i]时，将end更新为max(end, last_pos[s[i] - 'a'])，表示当前片段必须至少延伸到该字符的最后出现位置。
切分时机：当遍历指针i == end时，说明当前片段内的所有字符在后续字符串中都不会再出现，此时记录片段长度end - start + 1，并将start更新为end + 1。
结果返回：遍历结束后，result即为所有片段的长度列表。