✅DAY31 贪心算法终 | 56. 合并区间 | 738.单调递增的数字

56. 合并区间

解题思路：跟之前的重叠题差不多，重点在更新上，通过result里的值进行调整而不是在原数组上变动

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result=[]
        if len(intervals)==0: return result

        intervals.sort(key=lambda x:x[0])
        result.append(intervals[0])

        for i in range(1, len(intervals)):
            if result[-1][1] >= intervals[i][0]: # 发现重叠区间
                result[-1][1] = max(result[-1][1], intervals[i][1])
            else:
                result.append(intervals[i])  # 区间不重叠
        return result

738. 单调递增的数字

解题思路：从后往前遍历，取两位数，如果前一位>后一位，

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        strNum = list(str(n))

        for i in range(len(strNum)-1,0,-1):
            if strNum[i-1] > strNum[i]:
                flag = i
                strNum[i-1] =str(int(strNum[i-1]) -1)
                for j in range(i, len(strNum)):
                    strNum[j] = '9'

        return int(''.join(strNum))