贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。这种算法并不总是能找到全局最优解，但在某些问题上能提供足够好的解决方案。贪心算法的关键特性包括：
- 局部最优选择：在每一步决策时，都选择当前看来最佳的解决方案，不考虑长远的影响。
- 无后效性：过去做出的选择不会影响未来的选择，也就是说，当前的最优选择不会因为之前做了什么选择而改变。
- 贪心选择性质：问题需要具备贪心选择性质，即局部最优能导致全局最优或者部分最优解。
贪心算法适用于以下类型的问题：
- 最优装载问题：如背包问题的部分情况。
- 最小生成树问题：如Prim算法和Kruskal算法。
- 单源最短路径问题：如Dijkstra算法（非负权重时）。
- 活动安排问题：选择最多的互不冲突的活动。
例题：
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int val_5=0; int val_10=0;
for(int &val:bills){
if(val==5){
val_5++;
}else if(val==10){
val_10++;
val_5--;
}else if(val==20){
if(val_10>0){
val_10--;
val_5--;
}else{
val_5-=3;
}
}
if(val_5<0||val_10<0){
return false;
}
}
return true;
}
};2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）
class Solution {
public:
int halveArray(vector<int>& nums) {
priority_queue<double> heap;//val/2很可能为小数
double sum=0;//**1**使用 int，会导致sum/2，导致sum结尾
for(int& val:nums){
heap.push(val);
sum+=val;
}
int count=0;
sum/=2.0;
while(sum>0){//sum<=为结束条件，while和for需要运行条件，
double tmp=heap.top()/2.0;
heap.pop();
sum-=tmp;
heap.push(tmp);
count++;
}
return count;
}
};class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> strs;
for(int &val:nums) strs.push_back(to_string(val));
sort(strs.begin(),strs.end(),[](const string &s1,const string &s2){
return s1+s2>s2+s1;//"=" 不行，无法处理，导致string溢出
});
string ret="";
for(string &s1:strs) ret+=s1;
cout<<ret<<endl;
//处理前导零：
if(ret[0]=='0') return "0";
return ret;
}
};class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n=nums.size();
//if(n<2) return n;//**4**，初始化，其实n=0或者n=1不用特殊处理
int right=0,left=0;//**3**，初始化为0：统计初始结点。
int ret=0;
for(int i=0;i<n-1;i++){
right=nums[i+1]-nums[i];//**2**采用趋势记录，来判断波峰，波谷
if(right==0) continue;//***1**:跳过没有上升和下降的区间
if(right*left<=0) ret++;//**3**：“=”是为了将起始结点统计进ret;
left=right;
}
return ret+1;
}
};class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n=nums.size();
vector<int> ret;
ret.push_back(nums[0]);
for(int i=1;i<n;i++){
if(nums[i]>ret.back()){
ret.push_back(nums[i]);
}else{
int left=0; int right=ret.size()-1;
while(left<right){
int mid=left+(right-left)/2;//**1**，右区间的左端点，由于是左端点，所以right-left不用再+1，例如：[2,2],取左边的2，如果+1，取右边的2，错误
if(ret[mid]<nums[i]) left=mid+1;
else right=mid;
}
ret[left]=nums[i];
}
}
return ret.size();
}
};class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
vector<int> ret;
ret.push_back(nums[0]);
for(int i=1;i<n;i++){
if(nums[i]>ret.back()){
ret.push_back(nums[i]);
}else{
int left=0; int right=ret.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(ret[mid]<nums[i]) left=mid+1;
else right=mid;
}
ret[left]=nums[i];
}
if(ret.size()>=3) return true;
}
return false;
}
};class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int ret=1;
int n=nums.size();
int begin=0;int end=0;
while(begin<n){
end=begin+1;
while(end<n&&nums[end]>nums[end-1]){
ret=max(ret, end-begin+1);
cout<<"begin,end"<<begin<<" "<<end<<endl;
end++;//**1**满足条件后更新结果，循环条件的值应该在后面++
}
begin=end;
}
return ret;
}
};class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int _min=prices[0];
int ret_maxprofit=0;
for(int i=1;i<n;i++){
ret_maxprofit=max(ret_maxprofit,prices[i]-_min);
_min=min(_min,prices[i]);
}
return ret_maxprofit;
}
};122. 买卖股票的最佳时机 II - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int ret=0;
int begin=0; int end=0;
while(begin<n){
end=begin+1;
int tmp=0;
while(end<n&&prices[end]>prices[end-1]){
tmp=max(tmp,prices[end]-prices[begin]);
end++;
}
ret+=tmp;
begin=end;
}
return ret;
}
};1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
class Solution {
struct Greater{
bool operator()(int &a,int &b){//operator，运算符重载，一定记得加运算符，尤其是（）
return a>b;
}
};
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
// Greater Greater_1;
priority_queue<int,vector<int>,Greater> q;
int sum=0;
for(int &val:nums){
q.push(val);
sum+=val;
}
while(k){
if(q.top()<0){
int tmp=-q.top();
sum+=2*tmp;
q.pop();
q.push(tmp);
}else{
if(k%2==0){
return sum;
}else{
return sum-2*q.top();
}
}
k--;
}
return sum;
}
};class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n=names.size();
vector<int> v1;
for(int i=0;i<n;i++){
v1.push_back(i);
}
sort(v1.begin(),v1.end(),[&](int i,int j){//**1**[&]:引用上层代码块的变量
return heights[i]>heights[j];
});
vector<string> ret;
for(int &i:v1){
ret.push_back(names[i]);
}
return ret;
}
};class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size();
sort(nums1.begin(),nums1.end());
vector<int> index;
for(int i=0;i<n;i++) index.push_back(i);
sort(index.begin(),index.end(),[&](int i,int j){
return nums2[i]<nums2[j];
});
//田忌赛马
vector<int> ret(n);
int left=0; int right=n-1;
for(int &x:nums1){
if(x>nums2[index[left]]) ret[index[left++]]=x;//**1**ret下标与nums2中对应好
else ret[index[right--]]=x;
}
return ret;
}
};class Solution {
public:
int longestPalindrome(string s) {
int vis[128]={0};
for(char &ch:s){
vis[ch]++;
}
int ret=0;//**1**记得初始化。
int flag=0;//回文串最中间的那个数可以为单个
for(int i=0;i<128;i++){
if(vis[i]%2==0){
ret+=vis[i];
}else if(vis[i]%2==1){
ret+=vis[i]-1;
flag=1;
}
}
return flag==1?ret+1:ret;
}
};class Solution {
public:
vector<int> diStringMatch(string s) {
int left=0; int right=s.size();
vector<int> ret;
for(char &ch:s){
if(ch=='I') ret.push_back(left++);
else ret.push_back(right--);
}
ret.push_back(left);
return ret;
}
};class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int left=0; int right=g.size()-1;
int n=s.size();
int ret=0;
for(int i=0;i<n&&left<=right;i++){//**1**防止g下标溢出
if(s[i]>=g[left]) {
ret++;
left++;
}
}
return ret;
}
};class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n=nums.size();//策略: 看出分式，1：第一个数字一定在分子，第二个数必在分母 2：所以将分母变最小或将分子变最大，则两个是同一个操作，A/(B/C):将分母变小，==A*C/B：将分子变大
if(n==0) return 0;
else if(n==1){
return to_string(nums[0]);
}else if(n==2){
return to_string(nums[0])+'/'+to_string(nums[1]);
}
string ret=to_string(nums[0])+"/("+to_string(nums[1]);
for(int i=2;i<n;i++){
ret+="/"+to_string(nums[i]);
}
ret+=")";
return ret;
}
};class Solution {
public:
int jump(vector<int>& nums) {
int left=0; int right=0; int maxpos=0; int n=nums.size(); int ret=0;
while(left<=right){//循环条件，与left=right+1组合，判断是否不能够跳跃到下标n-1
if(maxpos>=n-1) return ret;//**1**maxpos表示最大能跳跃的position，所以>=n-1
for(int i=left;i<=right;i++){
maxpos=max(maxpos,nums[i]+i);//**2**nums[left]+left:表示跳跃的最大距离
}
left=right+1;
right=maxpos;
ret++;//表示一次
}
return -1;
}
};class Solution {
public:
bool canJump(vector<int>& nums) {
int left=0; int right=0; int maxpos=0;
while(left<=right){
if(maxpos>= nums.size()-1) return true;
for(int i=left;i<=right;i++){
maxpos=max(maxpos,nums[i]+i);
}
left=right+1;
right=maxpos;
}
return false;
}
};class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n=gas.size();
for(int i=0;i<n;i++){
int rest=0;//标记剩余汽油
int step=0;
for(;step<n;step++){
int index=(i+step)%n;
rest+=gas[index]-cost[index];
if(rest<0) break;//index无法到达index+1
}
if(step==n) return i;
i=i+step;
}
return -1;
}
};class Solution {
public:
int monotoneIncreasingDigits(int n) {//算法:找到最高并且递增的下标i，将s[i]--,其余低位变9
string s=to_string(n);
int m=s.size();
int i=0;
while(i<m-1&&s[i]<=s[i+1]) i++;
if(i==m-1) return n;//特殊情况
while(i-1>=0&&s[i-1]==s[i]) i--;
s[i]--;
for(int j=i+1;j<m;j++) s[j]='9';
return stoi(s);
}
};class Solution {
public:
int brokenCalc(int startValue, int target) {//正难则反：利用本题中target为偶数时,选择%2最优，仅奇数时，才+1
int ret=0;
while(target>startValue){
if(target%2==0) target/=2;
else target++;
ret++;
}
return ret+startValue-target;//startValue-target:表示target小于startValue时，所需的次数
}
};class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),[](vector<int> a,vector<int> b){
return a[0]<b[0];//不能等于，会判错，对于快排来说，没有稳定性，不用<=,a[0]<=b[0]会出错：显示vector访问越界，没有值就访问。
});
int n=intervals.size();
vector<vector<int>> ret;
int left=intervals[0][0]; int right=intervals[0][1];
for(int i=1;i<n;i++){
if(intervals[i][0]<=right){
right=max(right,intervals[i][1]);
}else{
ret.push_back({left,right});
left=intervals[i][0]; right=intervals[i][1];
}
}
ret.push_back({left,right});
return ret;
}
};class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
int n=intervals.size();
int ret=0;
int left=intervals[0][0]; int right=intervals[0][1];
for(int i=1;i<n;i++){
int a=intervals[i][0]; int b=intervals[i][1];
if(a<right){//找出重合中最大的区间。
ret++;
//int right=min(right,b);**1**从新定义错误，上面判断的a<right
//的right是上面的域的right
right=min(right,b);
}else{
left=a; right=b;
}
}
return ret;
}
};452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end());
int n=points.size();
int left=points[0][0]; int right=points[0][1];
int ret=0;
for(int i=1;i<n;i++){
int a=points[i][0]; int b=points[i][1];
if(a<=right){
right=min(b,right);
}else{
left=a; right=b;
ret++;
}
}
return ret+1;
}
};class Solution {
public:
int integerReplacement(long long n) {
int ret=0;
while(n>1){
if(n%2==0){
n/=2;
ret++;
}else{
if(n==3){//特例
ret+=2;
n=1;
}
else if(n%4==3){
n+=1;
ret++;
}else if(n%4==1){
n-=1;
ret++;
}
}
}
return ret;
}
};class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(),envelopes.end(),[](vector<int> &a,vector<int> &b){
return a[0]!=b[0]?a[0]<b[0]:a[1]>b[1];//必须降序，不降序的话，后面求最长递增子序列时，a[0]==b[0],a[1]>b[1],会被纳入序列中
});
int n=envelopes.size();
vector<int> ret;
ret.push_back(envelopes[0][1]);//ret;表示小标+1的长度的单调递增子序列的末尾最小数是什么。
for(int i=1;i<n;i++){
int b=envelopes[i][1];
if(b>ret.back()){
ret.push_back(b);
}else{
int left=0, right=ret.size();
while(left<right){
int mid=left+(right-left)/2;//二分求左区间的最小结点。左区间：>=target.
if(ret[mid]<b){
left=mid+1;
}else{
right=mid;
}
}
ret[left]=b;
}
}
return ret.size();
}
};1262. 可被三整除的最大和 - 力扣（LeetCode）
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int sum=0;
//最小
int INF=0x3f3f3f3f;
int x1=INF; int x2=INF;
int y1=INF; int y2=y1;
for(int &val:nums){
sum+=val;
if(val%3==1){
// int tmp=x1;//取最小值无法判断val在x1和x2之间
// x1=min(val,x1);
// if(x1==val) x2=tmp;
if(val<x1) {
x2=x1; x1=val;
}else if(val<x2){
x2=val;
}
}
if(val%3==2){
if(val<y1) {
y2=y1; y1=val;
}else if(val<y2){
y2=val;
}
}
}
if(sum%3==0) return sum;
else if(sum%3==2) return sum-min(y1,x1+x2);//超出int，两种情况二选一，其中有的情况不存在比如样例1中x1和x2不存在，但是应为是求最小值，初始化为INT_MAX不会被选取，但是相加会越界
else if(sum%3==1) return sum-min(x1,y1+y2);
return sum;
}
};class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
int n=barcodes.size();
unordered_map<int,int> hash;
int maxval=0;int maxcount=0;
for(int x:barcodes){
if(maxcount<++hash[x]){
maxcount=hash[x];
maxval=x;
}
}
vector<int> ret(n,0);
int index=0;
for(int i=0;i<maxcount;i++){
ret[index]=maxval;
index+=2;
}
hash.erase(maxval);
//index%=n;//**1**仅仅对n=奇数有效
for(auto& [x,count]:hash){
for(int i=0;i<count;i++){
if(index>=n) index=1;
ret[index]=x;
index+=2;
}
}
return ret;
}
};class Solution {
public:
string reorganizeString(string s) {
unordered_map<int,int> hash;
char max_ch=0; int max_count=0;
for(char& ch:s){
if(max_count<++hash[ch]){
max_count=hash[ch];
max_ch=ch;
}
}
if(max_count>(s.size()+1)/2) return "";
int n=s.size();
string ret;
ret.resize(n);
int index=0;
for(int i=0;i<max_count;i++){
ret[index]=max_ch;
index+=2;
}
hash.erase(max_ch);
for(auto& [x,count]:hash){
for(int i=0;i<count;i++){
if(index>=n) index=1;
ret[index]=x;
index+=2;
}
}
return ret;
}
};