力扣hot100 划分字母区间 贪心 思维 满注释版

Problem: 763. 划分字母区间

思路

👨‍🏫 代码随想录

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(n)$

Code

class Solution {public List<Integer> partitionLabels(String s){// 创建哈希表来存储我们记录到字符串中的元素的最后下标int[] right = new int[26];int n = s.length();for (int i = 0; i < n; i++)right[s.charAt(i) - 'a'] = i;ArrayList<Integer> res = new ArrayList<>();int l = 0;// 当前段的起点int r = 0;// 当前段的终点for (int i = 0; i < n; i++){
//			找到出现最远的字符,得到它的下标r = Math.max(r, right[s.charAt(i) - 'a']);if (i == r){res.add(r - l + 1);l = i + 1;//开启下一段的起点}}return res;}
}