day31-贪心__56. 合并区间__ 738.单调递增的数字__968.监控二叉树 （可跳过)

56. 合并区间

合并区间，这道题和昨天的452. 用最少数量的箭引爆气球和435. 无重叠区间 也是类似的思路，我们需要先对所有vector按照左端点或者右端点进行排序。本题按照左端点进行排序。之后，如果前一段的右端点<=后一段的左端，则进行合并操作，然后加入答案。否则就直接加入答案。

代码如下:

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间// 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠 }}return result;}
};

738.单调递增的数字

这道题，我们可以很容易的写出暴力代码。从题目所给num开始，不断的判断num-1 ~ 0，之间的每一个数字是否是单调递增(用/10 取余10的方法)。显然这样的时间复杂度是O（n*m） n为num的最大取值范围， m为num的最大位数。

代码如下:

class Solution {
private:// 判断一个数字的各位上是否是递增bool checkNum(int num) {int max = 10;while (num) {int t = num % 10;if (max >= t) max = t;else return false;num = num / 10;}return true;}
public:int monotoneIncreasingDigits(int N) {for (int i = N; i > 0; i--) { // 从大到小遍历if (checkNum(i)) return i;}return 0;}
};

在题目所给的数据量下， 这样的程序会超时。

那现在我们来考虑如何进行贪心呢，首先由于题目所给的是int类型的数字，这种数字不方便我们去遍历访问他的每一位以及后续的修改操作，所以这里，我们考虑将其先转换为string类型。然后，我们来看一下，如果是“233”这个例子，我们会发现它对应的最大递增是“229",并且对于"231"，按照题目的要求，它对应的也是"229"。也就是说，我们只要发现了存在strNum[i-1] >= strNum[i]时，就可以把strNum[i-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 = 1; i <= strNum.size()-1; i++) {if (strNum[i - 1] >= strNum[i] ) {flag = i;strNum[i - 1]--;break;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

这样看似逻辑正确对吗？但是提交到leetcode的发生这样的问题

因为如果我们从前向后遍历的话，先处理高位，就直接忽视了后面所有低位的情况，这样做出来的序列显然不是最大的递增序列。

现在我们考虑从后向前的考虑，这样我们能考虑到每一位的递增关系，并且确保它的局部最优叠加的总和是全局最优。

代码如下:

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);}
};

968.监控二叉树 （可跳过)

这道监督二叉树相当复杂，二刷再详细写解吧。

大家可以观看视频理解贪心算法，二叉树与贪心的结合，有点难… LeetCode:968.监督二叉树