LeetCode 763. 划分字母区间 java题解

https://leetcode.cn/problems/partition-labels/description/
贪心的

class Solution {public List<Integer> partitionLabels(String s) {ArrayList<Integer> res=new ArrayList<>();//返回每个区间的长度//记录每个字母最后一次出现的位置int[] nums=new int[26];char[] chars=s.toCharArray(); for(int i=0;i<chars.length;i++){nums[chars[i]-'a']=i;}int last=-1;//上一个区间的终点int index=0;//本区间的，最大结束位置（本区间所有字母的最后位置，其中最大的一个。从这以后，不会再出现本区间字母）for(int i=0;i<chars.length;i++){index=Math.max(index,nums[chars[i]-'a']);if(index==i){//当前就是本区间最大结束位置res.add(index-last);//加入结果。[last+1,index]last=index;//更新本区间终点}}return res;}
}