LintCode：1045. 分割标签

描述

给出一个由小写字母组成的字符串S。需要将这个字符串分割成尽可能多的部分，使得每个字母最多只出现在一个部分中，并且返回每个部分的长度。

个人思路:采取的贪心策略是，先遍历一次字符串，得到每个字符的结束的位置，第二次遍历字符串时，都将遍历到的字符的结束位置和之前记录的结束位置比较，最后取最远的结束位置，当i遍历到结束位置时，说明符合题目的要求

public List<Integer> partitionLabels(String S) {// Write your code here// Map<Character,Integer> endPosMap = new HashMap<>();// for(int i = 0; i<S.length(); i++){//     char ch = S.charAt(i);//     endPosMap.put(ch, i);            // }int[] endPosMap=new int[26];for(int i=0;i<S.length();i++){endPosMap[S.charAt(i)-'a']=i;}int lastEndPos = 0;int lastStartPos = 0;List<Integer> result = new ArrayList<>();for (int i = 0; i < S.length(); i++) {char ch = S.charAt(i);int endPos = endPosMap[ch - 'a'];if(i == 0)lastEndPos = endPos;if (i > lastEndPos){lastEndPos = endPos;}if(i < lastEndPos && endPos > lastEndPos){lastEndPos = endPos;}if(i == lastEndPos){result.add(lastEndPos - lastStartPos + 1);// r.add(S.substring(lastStartPos, lastEndPos+1));lastStartPos = lastEndPos + 1;}}return result;}

summary:1、如果要得到关于字符的缓冲区，采用endPosMap[S.charAt(i)-'a']=i这样的模式作缓冲区，这样既方便又直接

2、该题属于得到数量上的最值