代码随想录算法训练营第三十七天|56. 合并区间 738.单调递增的数字 968.监控二叉树 （可跳过）

LeetCode 56.合并区间

题目链接：56.合并区间

踩坑：昨天做了重叠区间的题，所以没踩坑。只是我们写的代码有点冗余，建议看卡哥的。

思路：首先对所有区间根据左边界从小到大排序，这样可以不考虑左边界的情况。依次比较相邻两区间的右边界和左边界，如果重叠则更新可覆盖区间的右边界。

代码：

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b)
    {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        vector<int> pair(intervals[0]);
        vector<vector<int>> result;
        for(int i = 0; i < intervals.size()-1; i++)
        {
            if(intervals[i][1] < intervals[i+1][0])
            {
                pair[1] = intervals[i][1];
                result.push_back(pair);
                pair = intervals[i+1];
            }
            else
            {
                intervals[i+1][1] = max(intervals[i][1], intervals[i+1][1]);
            }
        }
        pair[1] = intervals[intervals.size()-1][1];
        result.push_back(pair);
        return result;
    }
};

LeetCode 738.单调递增的数字

题目链接：738.单调递增的数字

踩坑：在判断的过程中不断的修改为9

思路：这个就是一道数学题，总结不出来规律就做不出来。规律就是，如果存在高位比低位大的情况，那么这个高位之后的所有位都要变成9，同时高位减一。

代码：

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        reverse(s.begin(), s.end());
        int flag = 0;
        for(int i = 1; i < s.length(); i++)
        {
            if(s[i] > s[i-1])
            {
                s[i]--;
                flag =  i;
            }
        }
        for(int i = 0; i < flag; i++)
        {
            s[i] = '9';
        }
        reverse(s.begin(), s.end());
        return stoi(s);
    }
};

LeetCode 968.监控二叉树

直接看视频，主要是贪心和分析的过程比较不好想