難度：★★★☆☆
類型：數(shù)組
方法：數(shù)學(xué)

力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄

給定一個非負整數(shù) N，找出小于或等于 N 的最大的整數(shù)，同時這個整數(shù)需要滿足其各個位數(shù)上的數(shù)字是單調(diào)遞增。

（當且僅當每個相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時，我們稱這個整數(shù)是單調(diào)遞增的。）

示例 1:

輸入: N = 10
輸出: 9

示例 2:

輸入: N = 1234
輸出: 1234

示例 3:

輸入: N = 332
輸出: 299
說明: N 是在 [0, 10^9] 范圍內(nèi)的一個整數(shù)。

解答

需要經(jīng)過兩次遍歷。

第一次遍歷，從最高位開始，尋找連續(xù)非遞減子串的最大長度，找到不再連續(xù)非遞減的位置。

第二次遍歷，從第一次遍歷找到的分界點開始向左遍歷，做退位相減，直到最高位。

最后，將分界點以后的所有位置成9即可。

class Solution(object):
    def monotoneIncreasingDigits(self, N):
        S = list(map(int, str(N)))

        i = 0
        while i < len(S) - 1 and S[i] <= S[i+1]:
            i += 1
        while 0 <= i < len(S) - 1 and S[i] > S[i+1]:
            S[i] -= 1
            i -= 1
        S[i+2:] = [9] * (len(S) - i - 2)
        return int("".join(map(str, S)))

如有疑問或建議，歡迎評論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請移步力扣中等題解析