贪心
解题思路
先理解 同一字母最多出现在一个片段中 是什么意思，举个 🌰：
- 字符串 “ababcbacadefegdehijhklij” 中第一个字母 a ，向后寻找 子字符串 能使的 a 只出现在这个 子字符串 中；
- 向后扫描的过程中，会出现 b、c 新字母，则也要保证 b、c 只出现在这个 子字符串 中；
- 最后找到的第一个 子字符串 是 “ababcbaca”；
具体步骤如下：
- 统计每一个字符最后出现的位置；
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是字符串的长度； -
空间复杂度：
O(∣Σ∣)，其中 Σ 是字符串中的字符集；这道题中，字符串只包含小写字母，因此∣Σ∣ = 26；
代码实现
var partitionLabels = function (s) {
// 1. 统计每一个字符最后出现的位置
let hash = {};
for (let i = 0; i < s.length; i++) {
hash[s[i]] = i;
}
let result = [];
let left = 0;
let right = 0;
// 2. 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
for (let i = 0; i < s.length; i++) {
right = Math.max(right, hash[s[i]]);
if (right === i) {
result.push(right - left + 1);
left = i + 1;
}
}
return result;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 452. 用最少数量的箭引爆气球
上一篇
评论
