力扣763-分别字母区间(Java具体题解)

题目链接：763. 分别字母区间 - 力扣（LeetCode）
前情提要：

因为本人近来都来刷贪婪类的题目所以该题就默认用贪婪方法来做。
贪婪方法：局部最优推出全局最优。
如果一个题你觉得可以用局部最优推出全局最优，并且没有反例来反驳的话就可以用贪婪来试试。
题目思路：

其实这个题入手很快，本题要求将字符划尽大概多的分为片段。其实贪婪就贪在，我们要找到尽大概长度小的片段。
局部最优：根据范围来得到最小的片段。
全局最优：得到尽大概多的片段。
那么我们怎么找呢？题目要求不同片段内，同一字母只能出现一次。
其实这题跟力扣55-跳跃游戏有点像。
   题目链接：55. 跳跃游戏 - 力扣（LeetCode） 题解链接： 力扣55-跳跃游戏（java具体题解）-CSDN博客
  如有须要，请自取。
  我们可以将每一个字母所出现的最大下标位置给求出，然后遍历该字符串，并在原来的最大范围内并扩大该范围，只有该范围不能再扩大了（即遍历到该片段的最大范围），那么这时求的就是最小的字符片段。
举个例子。

那么肯定就有人想，我们不是要求最小的片段吗，那这个片段的范围不是越小越好吗？怎么要求最大范围。
如果不如许，固然你的片段范围是小了，但是你的这个片段并不符合题意，题目要求不同片段内，同一字母只能出现一次。
你只有将该片段内的最大的字母下标位置确定下来，你才能确定该片段内所有的字母不会出现在其他的片段内。
核心思路就是要维护一个最大的边界范围，确定他的停止位置。
最终代码：

1. class Solution {
2.     public List<Integer> partitionLabels(String s) {
3.         //该题我们要寻找字符串尽可能多的片段，怎么求呢？
4.         //只要知道我们当前字母的最大范围，然后在我们的这个范围内再不断的扩大我们这个范围，只到我们不能再扩大了,那么我们就得到了这样一个最小的字符片段。
5.         //局部最优：根据范围来获得最小的片段
6.         //全局最优：获得尽可能多的片段
7.         int [] hashArr = new int [27];
8.         List<Integer> result = new ArrayList<>();
9.         //利用哈希思想，让每一个数组下标跟字母做映射，给每一个字母得出最大的位置下标
10.         for(int i = 0;i < s.length();i ++){
11.             hashArr[s.charAt(i) - 'a'] = i;
12.         }
13.         //在这里我们用双指针来获取每一个片段的长度
14.         //left记录起始位置 right记录终止位置
15.         int left = 0,right = 0;
16.         for(int i = 0;i <s.length();i ++){
17.             //首先 我们移动终止位置，知道终止位置移动到我们这个片段的最大下标位置就停止，收集结果
18.             //并让下一段起始位置移动到上一段终止位置的下一个
19.             right = Math.max(hashArr[s.charAt(i) - 'a'],right);
20.             if(right == i){
21.                 result.add(right - left + 1);
22.                 left = i + 1;
23.             }
24.         }
25.         return result;
26.     }
27. }

复制代码

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，大概私信我。
我很乐意为你解答。那么我们下篇再见！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。