【Day27】LeetCode：56. 合并区间，738. 单调递增的数字

LeetCode：56. 合并区间

https://leetcode.cn/problems/merge-intervals/

思路

1. 按区间左端点升序排序intervals。
2. 用区间[last_start, last_end]记录上一个正在合并的区间。然后遍历数组：
   （1）如果当前区间和正在合并的区间重叠：如果完全重叠就直接跳过；如果没有完全重叠，则更新正在合并的区间为[last_start, end]。
   （2）如果当前区间和正在的合并的区间不重叠：则说明上一个正在合并的区间可以合并结束，将合并后的区间加入结果，然后将当前区间作为正在合并的区间。
3. 最后将最后一个正在合并的区间添加进结果。

解答

classSolution:defmerge(self,intervals:List[List[int]])->List[List[int]]:n=len(intervals)intervals.sort(key=lambdax:x[0])# 按区间左端点升序排序results=[]last_start=intervals[0][0]last_end=intervals[0][1]forindex,intervalinenumerate(intervals[1:]):start=interval[0]end=interval[1]ifstart<=last_endandend>last_end:# 重叠且不完全覆盖last_end=endelifstart>last_end:# 完全不重叠，插入上一个results.append([last_start,last_end])last_start=start last_end=end results.append([last_start,last_end])# 插入最后一个returnresults

LeetCode：738. 单调递增的数字

https://leetcode.cn/problems/monotone-increasing-digits/description/

思路

倒序遍历数组，如果nums[i-1] > nums[i]，即出现递减，则标记flag = i，使得其后所有数都为9，然后nums[i-1]--。（例如出现324，因为3 > 2，所以标记数字 2 ，前一位 - 1，得到299）。

解答

classSolution:defmonotoneIncreasingDigits(self,n:int)->int:nums=list(str(n))flag=len(nums)# 标记从哪一位开始后面都是9foriinrange(len(nums)-1,0,-1):# 倒序遍历ifnums[i-1]>nums[i]:flag=i nums[i-1]=str(int(nums[i-1])-1)foriinrange(flag,len(nums)):nums[i]='9'returnint("".join(nums))