贪心 - wenzhoullq/leetcode GitHub Wiki
局部最优解满足全局最优解，局部最优解没有后置性,关键字最少/多/长/短
模拟取最值
D. Cloud of Hashtags-2023.1.13
维护一个最小值nums[],当前值与nums[i+1]进行比较
顺序访问，如果碰到不够的就加，或则将前面的去掉（用堆维护）
排序的方式需要直觉
754. 到达终点数字(一直加,加到和目标值差为偶数的时候返回,负数取绝对值
6152. 赢得比赛需要的最少训练时长 正常模拟，遇到不够的就补
用优先队列，对left进行排序，然后对最大值维护
Queue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
int len = ranges.length;
for(int i = 0; i < len ; i++ ){
q.add(new int[]{});
}
int ans = 0, max = 0 ;
while(max<n){
if(q.isEmpty()||q.peek()[0]>max) return -1;
int right = max;
while(!q.isEmpty()&&q.peek()[0] <= max) right = Math.max(right,q.poll()[1]);
if(right> max){
ans++;
max = right;
}
}
return ans;先排序，再使用贪心
Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
int ans=,right=points[0][1];
for(int i=1;i<points.length;i++){
if(right>=points[i][0]){
right=Math.(right,points[i][1]);//right处理
continue;
}
right=points[i][1];
}
return ans;
对于一般的块排序，我们通常会先进行快排，然后在正确的结果上进行对比，来确定相应的答案，模板如下。
int[] temp=(int[])arr.clone();
int max=arr[0],ans=0;
Arrays.sort(arr);
for(int i=0;i<arr.length;i++){
max=Math.max(max,temp[i]);
if(max==arr[i]) ans++;
}
return ans;如果会出现重复数字怎么办？把最大值改为区间和 然后接着深挖
int max=nums[0],min=nums[length-1];//max是用来确定排序的尾端的，即end;min是用来确定排序的首端的,即start
for(int i=0;i<nums.length;i++){
if(max>nums[i])//说明此处排序结尾仍然是混乱的，当出现max>nums[i],无论是nums有无排序过，只要出现，存在一个数x,[end-x,end]是混乱的
if(min<nums[i])//说明此处排序开头仍然是混乱的，当出现min<nums[i],无论是nums有无排序过，只要出现，存在一个数x,[start,start+x]是混乱的
}
while(str!=target){
1.找到不满足的且最大的位置
2.该位置到末尾翻转
3.ans++;
}
return ans;995. K 连续位的最小翻转次数 区间同一个数字的变化，还得用差分的思想
1529. 最少的后缀翻转次数 这题比较特殊，用区间翻转的思路可以，但是因为n太大了，会超时
2375. 根据模式串构造最小数字 因为要求字典序，因此先升序排序，然后对需要降序的部分进行反转
几个数字构成
数字之间存在关系，然后HashMap+贪心的思想去做
Arrays.sort(nums);
HashMap<Integer,Integer> m=new HashMap<>();
List<Integer> list=new LinkedList<>();
for(int temp:nums){
if(!m.containsKey(temp)) list.add(temp);
m.put(temp,m.getOrDefault(temp,0)+1);
}
for(int temp:list){
int num=m.get(temp);
if(num<0) return false;
if(num==0) continue;
//贪心处理
}消耗型贪心分两种，一种是减去具体的数，一种是除一个值，如果是除一个值的话，那么往往都伴随着+1/-1将其变为整除;无论是减法型贪心还是整除型贪心，他们都希望用最大的消耗（被减数最大，被除数最大）来先消耗，不足的再用别的来消耗
- 整除型消耗 模板有些粗糙，但是大概就是这个意思，即通过+1/-1的操作让n变得能被 2,3整除(2,3是题目给的)，因为+1/-1操作远不如整除操作，当被1和2处理的时候，时间复杂度较低，而当出现可以被多个数，如2，3整除，会出现重复计算，因此用记忆化dfs可以降低重复计算的量
main(int n,int target){
if() return ;//如果到了边界，return相应的值
return main(n%x+main(n/x))+1+n%x;//值得注意的是这里有个+1,即本次整除操作+1,而n%x则是+1操作
}- 减法型消耗
int mod=n%x;
if(mod==0) ans+=n/x;
else ans+=n/x+xx;991. 坏了的计算器 (正向情况太多,反向思考
1553. 吃掉 N 个橘子的最少天数 存在大量的重复计算，不如记忆化dfs
优先队列的本质是贪心
- 区间内最大差值的最小值
多指针+优先队列 每次取最小值
632. 最小区间 取优先队列的最后一个值有技巧,就是通过比较
- 拼接字符串
一般来说，给予几个字符a,b,c和他的数量，都是可以用优先队列来做的，但是时间复杂度相对较高
- 其他
当数据较小的时候，考虑暴力的方式进行贪心，如果变量是一个则双重for循环进行暴力贪心，如果变量多个则用回溯进行贪心
通过左边一次贪心和右边一次贪心得到，一般是跟相邻的比较或则同等位置的比较
838. 推多米诺 同2211
1671. 得到山形数组的最少删除次数 左右贪心+最长上升子序列
D2. Remove the Substring (hard version) 建立一个最早出现匹配和最晚出现匹配数组
存在着多少个与它相同
主要是建立映射，与它不同的还有多少，累计的是否超过了它
有点桶的思想
C. Maximum Median - 2023.4.10-灵茶 值得注意的是,k不能先减,因为arr[i] 和 arr[i-1]可能相差特别大,但是k均匀分布到前面还是可能的
6144. 将数组排序的最少替换次数 从右往左拆，拆的值取平均值
当全部完成一轮后+1
俩俩抵消都是最大的两个抵消的