贪心算法part05

文章参考来源代码随想录 (programmercarl.com)

56. 合并区间

本题和前几题类似，都是判断上一个元素的右边界与当前元素的左边界大小关系

但是需要注意是：本题需要更新结果数组元素的右边界，因此比较的是数组最后一个元素右边界与当前元素左边界大小通过back（）方法更新；

此外，在排序之后，结果数组应直接存入目标数组的第一个元素，方便之后更新。

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) {
        vector<vector<int>>result;
        sort(intervals.begin(),intervals.end(),cmp);
        result.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            if(result.back()[1]>=intervals[i][0]){
                result.back()[1]=max(result.back()[1],intervals[i][1]);
            }
            else{
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

738.单调递增的数字

暴力解法

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

贪心算法

例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

这一点如果想清楚了，这道题就好办了。

此时是从前向后遍历还是从后向前遍历呢？

从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。

这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

所以这里先判断前一个元素是否大于当前元素，大于的话，flag标记位置，前一个元素减小

之后从flag开始到最后一位均赋值为9

flag初始化为s.size（）

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