D15

鲁迅曾说，尽量每天都让自己充实一点，你可以刷一个小时的短视频，打一个小时的王者荣耀，但尽量再留一个小时出来读一下书、教程、博客，让自己的大脑保持活跃，而不是垃圾场。如果真的没有事情做，刷 LeetCode 确实是一个不错的选择。好，今天继续坚持来一道 LeetCode 题解，第18 题——划分字母区间

划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

有了前两道跳跃游戏的练习(见上次题解博客)，再看到这种贪心的题目，我们即使不能一下子全想出来解法，也有点思路了。这道题目我第一眼，直觉告诉我要找某个字母最后出现的位置，但也仅仅到这了。。。去看了题解。

这道题目贪心的核心：

记录所有字母最大索引位置
当前第i个字母的最大索引位置作为区间最右端
如果当前位置就处在当前序列某字母的最大索引，则将这一序列归为一个片段

我们来详细解释一下为什么是这样。

比如我有一序列ababcc，从索引0开始遍历字符串，首先获得a的最大索引是2，那么记录end = 2，索引为1时，b的最大索引是3，更新end = 3，直到索引为3时，end也是3，所以就代表当前字母仅在这一序列中，将end作为区间右端点，这就是第一段区间。

可能有人问，为什么通过最大索引就能把字母们分好类呢？

首先，题目要求是同一字母只能出现在一个序列中，这个例子中因为a最大索引是2，所以在2之前所有的字母都与a强行绑定了，也就是说，他们必须在一个序列中，所以当我们每次都获取当前字母的最远位置，不断更新区间的右端点，凡是包括在内部的字母都在一个序列中，直到当前位置到了记录的最大索引。此时，不再有新的字母加入，并且也到了内部字母能到的最远位置。

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> ans = new ArrayList();int[] far = new int[26]; //记录某个字母存在的最远距离char[] ss = s.toCharArray();for (int i = 0; i < ss.length; i++) {far[ss[i] - 'a'] = i;}int end = 0;int start = 0;for(int i = 0; i < ss.length; i++){end = Math.max(end, far[ss[i] - 'a']); //当前字母存在的最远位置if(end == i){ans.add(end - start + 1);start = i + 1;}}return ans;}
}