763. 划分字母区间（贪心算法）

763. 划分字母区间

• 题目
• 解题思路
• 代码

题目

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

提示：

• S的长度在[1, 500]之间。
• S只包含小写字母 ‘a’ 到 ‘z’ 。

解题思路

• 1、记录每个字母在S中最后出现的下标
• 2、从下标0开始尝试分段，左边界left是0
• 3、“同一个字母必须在同一片段中”,所以初始right是该段首字母最后出现的位置
• 4、动态遍历left到right，如果有字符最后出现的下标大于right，更新right
• 5、遍历完成后，一个分段就生成了。计数区间长度，更新left = right + 1，转3继续。

代码

class Solution {
   public  List<Integer> partitionLabels(String S) {

        Map<Character,Integer> map=new HashMap<>();//用来存放每个元素的最后出现的位置下标

        char[] s = S.toCharArray();//toCharArray() 方法将字符串转换为字符数组。

        for (int i = 0; i <s.length ; i++) {
                map.put(s[i],i);//一轮遍历完了以后，元素最后一次出现的位置被存放到了map中。
        }

        int left=0;
        int right=map.get(s[0]);//right被初始化为第一个元素最后出现的位置

        List<Integer> result=new ArrayList<>();

        while (left<=right){//之所要等号，是考虑到数组的第一个元素有且仅有一个，这样left和right都是0，如果没有等号就进不了循环
            for (int i = left; i <right ; i++) {
                if (map.get(s[i])>right){//如果在初始的left--right区间内，有元素的最后出现位置大于初始的right，则更新right。
                    right=map.get(s[i]);
                }
            }
            result.add(right-left+1);//第1、2、3、4...个区间的长度

            left=right+1;//上面的循环结束后，求出了第一个区间，第二个区间的left为上一轮得到的right+1，这轮的初始right为map.get(right+1)

            if (left-1==(s.length-1)){//如果已经到了最后一个区间了：那么上轮循环结束后的right+1就是s的length。 即这一轮的left-1==上一轮的right ==s.length-1
                right=left-1; //让right比left小1 跳出循环
            }else{
                right=map.get(s[right+1]);
            }


        }


        return result;
    }
}