• 🙋‍♂️ 作者：海码007
• 📜 专栏：算法专栏
• 💥 标题：【Hot 100】763. 划分字母区间
• ❣️ 寄语：书到用时方恨少，事非经过不知难！

引言

划分字母区间

• 🎈 题目链接：
• 🎈 做题状态：

我的解题

为了解决“每个字母最多只出现在一个区间中”的问题，采用的是贪心策略，目标是在遍历过程中尽早确定每一个可以独立划分的区间。整个解题思路可以分为两个主要阶段：

---

一、记录每个字母的最远出现位置

我们首先需要知道每个字符的最右侧位置（即最后一次出现的位置），这样在遍历时就能判断一个区间内的所有字符是否都已经包含完整。由于题目中限定字符串由小写字母组成，因此可以直接使用一个大小为 26 的整型数组 last[26]，通过 s[i] - 'a' 将字符映射到对应数组下标。在一次遍历中，我们将每个字符的最新索引位置记录下来。

---

二、扫描字符串并进行贪心划分

在第二轮遍历中，我们从左到右扫描字符串。使用两个变量：

• start 表示当前区间的起点；
• end 表示当前区间中所有字符的最远右边界（可能会动态扩大）。

每访问一个字符 s[i]，就将 end 更新为 max(end, last[s[i]])，也就是说当前区间至少要覆盖这个字符的最远位置。如果我们发现当前位置 i 正好等于 end，说明当前区间中的所有字符都不会再在后续出现了，此时可以安全地进行一次划分，并将该区间长度 end - start + 1 添加到结果数组中。随后更新 start = end + 1，开启下一段区间的判断。

---

class Solution {
public:vector<int> partitionLabels(string s) {int last[26];  // 记录每个字母的最后一次出现位置int length = s.size();// 第一步：记录每个字符的最右侧位置for (int i = 0; i < length; ++i) {last[s[i] - 'a'] = i;}vector<int> partition;int start = 0, end = 0;// 第二步：遍历并划分区间for (int i = 0; i < length; ++i) {end = max(end, last[s[i] - 'a']);  // 扩大当前分段右边界// 到达当前分段的终点，开始划分if (i == end) {partition.push_back(end - start + 1);  // 记录长度start = end + 1;  // 开启新分段}}return partition;}
};