题型1、2个维度的要求
战略：
不能顾此失彼，先从一个维度下手，再解决另个维度的问题
典型例题：
题型2、区间问题
战略：
先考虑如何排序，根据排序后的结果贪心实现
典型例题：
以上本质都是在求有几个重叠区段
56. 合并区间
为什么不能按照右端排序？
题型3、763. 划分字母区间
战术：
利用双指针划定当前区间端
public List<Integer> partitionLabels(String s) {
int start = 0;
int end = 0;
int[] arr = new int[26];
Arrays.fill(arr, -1);
List<Integer> resultList = new ArrayList<>();
for (int i=0; i<s.length(); ++i) {
// 双指针找到一组子字符串的end
while (i<=end) {
char ch = s.charAt(i);
if (arr[ch-'a']==-1) {
// 找到当前字符的end
int j = s.length()-1;
for (; j>=i; --j) {
if (s.charAt(j) == ch) {
break;
}
}
arr[ch-'a'] = j;
}
end = Math.max(end, arr[ch-'a']);
i++;
}
resultList.add(end-start+1);
start = i;
end = start;
i--;
}
战术改进：
因为是26个小写字母，可以用26长度的int数组表示每个字母在字符串中最后的位置。其实双指针也是 为了找到最后的字母位置。但是这种方法限定了，必须提前知道字符串的范围是哪些字符组成。
public List<Integer> partitionLabels(String s) {
int[] position = new int[26];
Arrays.fill(position, -1);
char[] ch = s.toCharArray();
for (int i=0; i<ch.length; ++i) {
position[ch[i]-'a'] = i;
}
List<Integer> result = new ArrayList<>();
int start = -1;
int end = 0;
for (int i=0; i<ch.length;++i) {
end = Math.max(position[ch[i]-'a'], end);
if (end == i) {
result.add(end-start);
start=end;
}
}
return result;
}
题型4、738. 单调递增的数字
战术：非贪心的做法
找到第一个不单调的位置，包括相等的，变该位置为当前数字-1，在该位置后面的变9。为方便处理，数字要改字符串处理，这一点可以引申，以后遇到类似问题注意处理。
public int monotoneIncreasingDigits(int n) {
String[] strings = (n+"").split("");
int[] position = new int[10];
Arrays.fill(position, -1);
int start = -1;
for (int i=0; i<strings.length; ++i) {
int num = Integer.parseInt(strings[i]);
if (position[num] == -1){
position[num] = i;
}
if (i>0){
int a = Integer.parseInt(strings[i-1]);
int b = Integer.parseInt(strings[i]);
if (a>b) {
start = position[a];
break;
}
}
}
if (start==-1) {
return n;
} else {
strings[start] = (Integer.parseInt(strings[start])-1)+"";
for (int i=start+1; i<strings.length; ++i) {
strings[i] = "9";
}
}
return Integer.parseInt(String.join("",strings));
}
战术改进：找到第一个不单调的位置，并不容易，代码也比较冗长，同时使用了position保存数字首次出现的位置，内存消耗高。如何改进？
逆向遍历，如果nums[i]<nums[i-1], 记录i的位置，同时nums[i-1]-1。
public int monotoneIncreasingDigits(int n) {
String[] strings = (n + "").split("");
int start = strings.length;
for (int i = strings.length - 1; i > 0; i--) {
if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
start = i;
}
}
for (int i=start; i<strings.length; ++i) {
strings[i] = "9";
}
return Integer.parseInt(String.join("",strings));
}
