力扣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;
	}
}