代码随想录算法训练营day31 | 贪心算法 | 56. 合并区间、738.单调递增的数字

本文主要是介绍代码随想录算法训练营day31 | 贪心算法 | 56. 合并区间、738.单调递增的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 56. 合并区间
- - 思路
- 738.单调递增的数字
- - 思路
- 贪心算法专题总结

今天是贪心算法专题的第5天，是贪心算法专题的最后一天

56. 合并区间

建议：本题也是重叠区间问题，如果昨天三道都吸收的话，本题就容易理解了

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

思路

左边界排序数组，记录重叠区间的起始位置start 和终止位置end。

如果end >= intervals[i] [0]，则说明intervals[i]在当前的重叠区间内，更新end = max(end, intervals[i][1]);
否则，intervals[i]不在当前的重叠区间内，将当前重叠区间合并，即result.push_back({start, end})，然后更新start 和 end

代码实现：

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b){return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;sort(intervals.begin(), intervals.end(), cmp);int end = intervals[0][1];int start = intervals[0][0];for(int i=0; i<intervals.size(); ++i){if(end >= intervals[i][0]){end = max(end, intervals[i][1]);}else{result.push_back({start, end});start = intervals[i][0];end = intervals[i][1];}}result.push_back({start, end});	// 不要忘了合并最后一个重叠区间return result;}
};

738.单调递增的数字

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

思路

首先将数字转化为字符串strNum，方便后续处理。本题只需要想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了

这样，我们从后向前遍历，重复利用上次比较得出的结果，找到最后一处strNum[i - 1] > strNum[i]的位置i，用flag记录这个位置i，从flag到末尾都赋值为9，strNum就是最终结果

以332为例，332->329->299，flag=1，从下标1到最后，将所有的位置都赋值9

代码如下：

class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);// flag用来标记赋值9从哪里开始// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行int flag = strNum.size();for(int i=strNum.size()-1; i>0; --i){if(strNum[i-1] > strNum[i]){flag = i; strNum[i-1]--;}}for(int i=flag; i<strNum.size(); ++i){strNum[i] = '9';}return stoi(strNum);}
};