算法第27天|贪心算法：合并区间 、单调递增的数字

合并区间 

题目链接：56. 合并区间 - 力扣（LeetCode）

代码随想录

整体思路：
        同意区间，合并区间，记录

整体代码：

class Solution {
public:

    //sort函数的cmp
    static bool cmp(const vector<int>&a ,const vector<int>&b)
    {
        if(a[0]<b[0])return true;
        else if(a[0]==b[0])
        {
            if(a[1]<b[1])return true;
        }
        return false;
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //排序
        sort(intervals.begin(),intervals.end(),cmp);
        //定义一个结果
        vector<vector<int>>res;
        //定义左端点，右端点
        int left = intervals[0][0];
        int right = intervals[0][1];
        //如果区间集合中没有或者只有一个
        if(intervals.size()==0)return {{0,0}};
        else if(intervals.size()==1)return {{left,right}};
        //for循环遍历
        for(int i=1;i<intervals.size();i++)
        {
            //判断当前是否重叠
            if(intervals[i][0]<=right)//当前区间的左端点小于等于前一个区间的右端点位置，就是重叠的
            {
                //更新右端点
                right = max(right,intervals[i][1]);
            }
            else if(intervals[i][0]>right)//当前区间的左端点与上一个区间没有重叠
            {
                //记录上一个区间
                res.push_back({left,right});
                //将左右端点位置更新
                left = intervals[i][0];
                right = intervals[i][1];
            }
            //如果最后一个区间，只是加进去了，但是没有记录
            if(i==intervals.size()-1)
            {
                res.push_back({left,right});
            }

        }
        return res;
    }
};

单调递增的数字

题目链接：738. 单调递增的数字 - 力扣（LeetCode）

代码随想录

整体思路：

        从后往前遍历，当前数字比前一个数字大，就将前边的所有数字变为9，当前数字减1，
因为比较的是当前数字与右边数字的大小，更改的是当前数字的大小（当前-1）,所以其实顺序是从右向左才能将右边更改了的不动，更改左边的不会影响右边的数字

整体代码：

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        //从后往前遍历，当出现当前数字大于前一个数字的时候，就让当前数字-1，前边所有位置变成9
        //因为是数字，所以需要取余10记录最低位置是多少
        int vec =0;//记录最小位置的数字
        vector<int>res;//记录每一个位置上的数字，注意是反方向的
        while(n!=0)
        {
            vec = n%10;
            if(res.size()==0)
            {
                res.push_back(vec);
            }
            else
            {
                if(vec>res[res.size()-1])//如果当前的数字大于前边一位的数字，当前数字减1，其余数字全部变成9
                {
                    vec = vec-1;
                    for(int i=0;i<res.size();i++)
                    {
                        res[i] = 9;
                    }
                    res.push_back(vec);
                }
                else//否则正常添加数字
                {
                    res.push_back(vec);
                }
            }
            n = n/10;//下一次的大小
        }
        //统计数字是多少
        long long sum =0;
        for(long long i=0,j=1;i<res.size();i++)
        {
            sum += res[i]*j;
            j  *= 10;
        }
        return sum ;
    }
};