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

合并区间 

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

代码随想录

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

整体代码：

class Solution {public: //sort函数的cmp static bool cmp(const vector&a ,const vector&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> merge(vector<vector>& intervals) { //排序 sort(intervals.begin(),intervals.end(),cmp); //定义一个结果 vector<vector>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)//当前区间的左端点与上一个区间没有重叠 { //记录上一个区间 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;//记录最小位置的数字 vectorres;//记录每一个位置上的数字，注意是反方向的 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 ; }};