Open youngyangyang04 opened 3 months ago
int[] hash = new int[26];
for (int i = 0; i < S.length(); i++) {
hash[S.charAt(i) - 'a'] = i;
}
List<Integer> result = new ArrayList<>();
int left = 0, right = 0;
for (int i = 0; i < S.length(); i++) {
right = Math.max(right, hash[S.charAt(i) - 'a']);
if (i == right) {
result.add(right - left + 1);
left = right + 1;
}
}
return result;
// 例: s = "ababcbacadefegdehijhklij", left = 0, right = 0
i = 0: right = 8, 不满足 i == right,继续遍历 ...
i = 8: right = 8, 满足 i == right,result = [9], left = 9 ...
i = 10: right = 15, 不满足 i == right,继续遍历 ...
i = 15: right = 15, 满足 i == right,result = [9,7], left = 16 ...
i = 18: right = 23, 不满足 i == right,继续遍历 ...
i = 23: right = 23, 满足 i == right,result = [9,7,8], left = 24
在补充中,用左边界再做排序多余了,排序已经在 countLabels中体现过了。
https://www.programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html