0738._Monotone_Increasing_Digits.md

738. Monotone Increasing Digits

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/monotone-increasing-digits/

内容描述

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:
Input: N = 10
Output: 9
Example 2:
Input: N = 1234
Output: 1234
Example 3:
Input: N = 332
Output: 299
Note: N is an integer in the range [0, 10^9].

解题方案

思路 1 - 时间复杂度: O(D^2)- 空间复杂度: O(D)******

贪心，从第一位数字开始构造，每次构造出最大的满足条件的prefix

beats 58.46%

class Solution:
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """        
        digits = []
        A = list(map(int, str(N)))
        for i in range(len(A)):
            for d in range(1, 10):
                if digits + [d] * (len(A)-i) > A:
                    digits.append(d-1)
                    break
                elif d == 9:
                    digits.append(9)

        return int(''.join(map(str, digits)))

思路 2 - 时间复杂度: O(D)- 空间复杂度: O(D)******

跟solution的想法一样，比如333222

• 先找到第一个32不符合要求，然后我们将3减去1变成2，后面的所有都变成9，于是333222 -> 332999
• 然后对于332999，我们发现32不符合要求，然后我们将3减去1变成2，后面的所有都变成9，于是332999 -> 329999
• 然后对于329999，我们发现32不符合要求，然后我们将3减去1变成2，后面的所有都变成9，于是329999 -> 299999

最后满足了直接返回

时间复杂度中的D是指输入N的数字位数

beats 98.46%

class Solution:
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        digits = list(str(N))
        idx = 1
        while idx < len(digits) and digits[idx-1] <= digits[idx]:
            idx += 1
        while 0 < idx < len(digits) and digits[idx-1] > digits[idx]:
            digits[idx-1] = str(int(digits[idx-1]) - 1)
            idx -= 1
        digits[idx+1:] = ['9'] * (len(digits)-idx-1)
        return int(''.join(digits))