[M贪心+双指针] lc763. 划分字母区间(贪心+双指针)

文章目录

1. 题目来源2. 题目说明3. 题目解析方法一：贪心+双指针

1. 题目来源

链接：763. 划分字母区间

2. 题目说明

3. 题目解析

方法一：贪心+双指针

一个字母只能出现在同一个片段，则需要求出一个字母出现的最后一次下标位置，这个采用 hash 扫一遍字符串就可以了。

关键是怎么求出尽可能多的片段？

简单想了一个思路就是：

从左至右遍历字符串，维护一个片段区间的左右端点下标 l、r，初始化均为 0每个字母都技能在这个片段中出现一次，那么这个片段的 r 就是本片段所有字母最后出现位置的最大值记当前字母的最后一次下标为$has{h}_i$，故每次更新 $r=max(r,has{h}_i)$那么当 i 遍历到与 r 相等的时候，就是唯一确定了一个片段，且这个片段长度最小，故得到的片段数也是最多的

贪心算法大多难以证明，或者采用反证法，貌似这个不太好给出好的证明，从直观上来讲确实是正确的。 挖坑后补。

参见代码如下：

class Solution { public: vector<int> partitionLabels(string S) { int n = S.size(); int hash[26] = {0}; for (int i = 0; i < n; ++i) hash[S[i] - 'a'] = i; vector<int> res; int l = 0, r = 0; for (int i = 0; i < n; ++i) { r = max(r, hash[S[i] - 'a']); if (i == r) res.push_back(r - l + 1), l = r + 1; } return res; } };