贪心算法---划分字母区间

题目：

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

思路:非贪心思路

先遍历一遍字符串记录所有字母最后出现的下标，再遍历一遍字符串更新字符出现的最远下标，如果找到字符最远出现的位置下标和当前下标相等，则找到了分割点。

代码：

    public List<Integer> partitionLabels(String s) {int hash[]=new int[26];//记录每个字符的最后一次出现的下标List<Integer> result=new LinkedList<>();//记录最后的结果char[] chars=s.toCharArray();for(int i=0;i<chars.length;i++){hash[chars[i]-'a']=i;}int left=0;//记录区间的左边界int right=0;//记录区间的右边界for(int i=0;i<chars.length;i++){right=Math.max(right,hash[chars[i]-'a']);//更新区间的最右边界if(i==right){result.add(right-left+1);//将该区间的长度加入结果集left=i+1;//更新下一个区间的左边界}}return result;}