題型1、2個(gè)維度的要求
戰(zhàn)略：
不能顧此失彼，先從一個(gè)維度下手召夹，再解決另個(gè)維度的問題
典型例題：
? 135. 分發(fā)糖果
? 406. 根據(jù)身高重建隊(duì)列
題型2滥嘴、區(qū)間問題
戰(zhàn)略：
先考慮如何排序动羽，根據(jù)排序后的結(jié)果貪心實(shí)現(xiàn)
典型例題：
? 452. 用最少數(shù)量的箭引爆氣球
? 435. 無重疊區(qū)間
以上本質(zhì)都是在求有幾個(gè)重疊區(qū)段
? 56. 合并區(qū)間
為什么不能按照右端排序句喷？
題型3镣典、763. 劃分字母區(qū)間
戰(zhàn)術(shù)：
利用雙指針劃定當(dāng)前區(qū)間端
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) {
// 找到當(dāng)前字符的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--;
}
戰(zhàn)術(shù)改進(jìn)：
因?yàn)槭?6個(gè)小寫字母，可以用26長度的int數(shù)組表示每個(gè)字母在字符串中最后的位置唾琼。其實(shí)雙指針也是 為了找到最后的字母位置兄春。但是這種方法限定了，必須提前知道字符串的范圍是哪些字符組成锡溯。
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. 單調(diào)遞增的數(shù)字
戰(zhàn)術(shù)：非貪心的做法
找到第一個(gè)不單調(diào)的位置，包括相等的祭饭，變?cè)撐恢脼楫?dāng)前數(shù)字-1芜茵，在該位置后面的變9。為方便處理倡蝙，數(shù)字要改字符串處理九串，這一點(diǎn)可以引申，以后遇到類似問題注意處理寺鸥。
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));
}
戰(zhàn)術(shù)改進(jìn)：找到第一個(gè)不單調(diào)的位置猪钮，并不容易，代碼也比較冗長析既，同時(shí)使用了position保存數(shù)字首次出現(xiàn)的位置躬贡，內(nèi)存消耗高。如何改進(jìn)眼坏？
逆向遍歷拂玻，如果nums[i]<nums[i-1], 記錄i的位置，同時(shí)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));
}
