当前位置：首页 > news >正文

【Hot 100 刷题计划】 LeetCode 763. 划分字母区间 | C++ 贪心算法题解

news 2026/3/26 17:31:16

LeetCode 763. 划分字母区间 | C++ 贪心算法题解

📌 题目描述

题目级别：中等

给你一个字符串s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

例如，字符串"ababcc"能够被分为["abab", "cc"]，但类似["aba", "bcc"]或["ab", "ab", "cc"]的划分是非法的。

注意：划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是s。
返回一个表示每个字符串片段的长度的列表。

💡 解题思路：贪心算法

要满足“同一字母最多出现在一个片段中”，核心逻辑是：一旦某个字母出现在当前的片段中，那么这个片段的右边界，至少要扩展到该字母在整个字符串中最后一次出现的位置。

我们可以通过两次遍历完美解决（贪心策略）：

1. 记录每个字母的“最远边界”

首先遍历一次字符串s，使用一个数组或哈希表记录下每个字母最后一次出现的下标位置。

2. 动态维护当前片段的右边界

使用双指针l（当前片段的左端点）和r（当前片段的右端点），再次遍历字符串：

每次遇到一个字母s[i]，我们就去查它的最后出现位置，并尝试更新当前片段的右边界：r = max(r, 该字母最后出现的位置)。
高光时刻（切分条件）：当我们继续往后遍历，直到遍历指针i走到了当前片段的右边界r（即i == r）时，说明当前片段内的所有字母，在后面都不会再出现了！这时我们就可以安心地在这里“切一刀”。
记录下当前片段的长度r - l + 1，并将左指针l更新为r + 1，准备寻找下一个片段。

💻 C++ 代码实现

classSolution{public:vector<int>partitionLabels(string s){intn=s.size();// 记录每个小写字母最后一次出现的下标// 开辟大小为 30 的数组（26 个字母足够，30 防溢出）vector<int>last(30);for(inti=0;i<n;i++){last[s[i]-'a']=i;}vector<int>res;intl=0;// 当前片段的左边界intr=0;// 当前片段的右边界for(inti=0;i<n;i++){// 不断刷新当前片段必须包含的最远右边界r=max(r,last[s[i]-'a']);// 当遍历到右边界时，说明 [l, r] 内的所有字母都不会在更后面出现了if(i==r){res.push_back(r-l+1);// 记录当前片段长度l=r+1;// 开启下一个片段}}returnres;}};