代码随想录算法训练营第三十一天| LeetCode 56 合并区间、LeetCode 738 单调递增的数字

参考文章均来自代码随想录LeetCode 56 合并区间参考文章链接以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。示例 1 输入intervals [[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]] 解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2 输入intervals [[1,4],[4,5]] 输出[[1,5]] 解释区间 [1,4] 和 [4,5] 可被视为重叠区间。 示例 3 输入intervals [[4,7],[1,4]] 输出[[1,7]] 解释区间 [1,4] 和 [4,7] 可被视为重叠区间。一样的套路先排序让所有的相邻区间尽可能的重叠在一起按左边界或者右边界排序都可以处理逻辑稍有不同。 如参考文章图所示用合并区间后左边界和右边界作为一个新的区间加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。classSolution{public:vectorvectorintmerge(vectorvectorintintervals){vectorvectorintresult;if(intervals.size()0)returnresult;// 区间集合为空直接返回sort(intervals.begin(),intervals.end(),[](constvectorinta,constvectorintb){returna[0]b[0];});result.push_back(intervals[0]);for(inti1;iintervals.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]);}}returnresult;}};时间复杂度: O(nlogn)空间复杂度: O(logn)排序需要的空间开销LeetCode 738 单调递增的数字参考文章链接当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。示例 1: 输入: n 10 输出: 9 示例 2: 输入: n 1234 输出: 1234 示例 3: 输入: n 332 输出: 299本题只要想清楚个例例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]减一strNum[i]赋值9这样这个整数就是89。就可以很自然想到对应的贪心解法了。此时是从前向后遍历还是从后向前遍历呢从前向后遍历的话遇到strNum[i - 1] strNum[i]的情况让strNum[i - 1]减一但此时如果strNum[i - 1]减一了可能又小于strNum[i - 2]。这么说有点抽象举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299确定了遍历顺序之后那么此时局部最优就可以推出全局找不出反例试试贪心。classSolution{public:intmonotoneIncreasingDigits(intN){string strNumto_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值为了防止第二个for循环在flag没有被赋值的情况下执行intflagstrNum.size();for(intistrNum.size()-1;i0;i--){if(strNum[i-1]strNum[i]){flagi;strNum[i-1]--;}}for(intiflag;istrNum.size();i){strNum[i]9;}returnstoi(strNum);}};时间复杂度O(n)n 为数字长度空间复杂度O(n)需要一个字符串转化为字符串操作更方便