贪心算法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);}
};