5 4 votes
Article Rating
Subscribe
提醒
guest
6 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
sunznx
// CreateTime: 2020-12-15 02:54:57
class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        auto str = to_string(N);


        auto maxIdx = 0;
        for (int i = 0; i < str.size()-1; i++) {
            if (str[i] > str[maxIdx]) {
                maxIdx = i;
            }


            if (str[i] > str[i+1]) {
                str[maxIdx] -= 1;
                for (int j = maxIdx+1; j < str.size(); j++) {
                    str[j] = '9';
                }
                break;
            }
        }


        return stoi(str);
    }
};
王半仙儿

思路:
1.从高位到低位遍历——这个保证最大
2.不满足的换为999——这个保证递增

高位尽可能不变(因为要最大的数),从高到低第一个满足 

str[i] > str[i+1]的位置,把剩下的换成9.这样最大的递增的数就找到了。

调试的时候,发现一个bad case:

n = 23331, res = 22999,计算res的时候,会有回退操作

class Solution(object):
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        s = str(N)
        max_index = ''
        idx = -1
        res = [''] * len(s)
        for i in range(len(s)):
            if s[i] > max_index:
                max_index = s[i]
                idx = i
                res[i] = s[i]
            if s[i] == max_index:
                res[i] = s[i]
            if i < len(s) - 1 and s[i] > s[i + 1]:
                tmp = int(s[idx]) - 1
                res[idx] = str(tmp)
                for j in range(idx + 1, len(s)):
                    res[j] = '9'
                break
        a = ''.join(res)
        b = int(a)
        return b

暴走的楚狂
"""" python
class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        if N < 10:
            return N
        else:
            N_list = [int(n) for n in str(N)]
            digits_N = len(N_list)
            for i in range(1, digits_N):
                if N_list[i] < N_list[i-1]:
                    break

            while i >= 1:
                if N_list[i] < N_list[i-1]:
                    N_list[i-1] -= 1
                    i -= 1
                else:
                    break

            for n in range(i+1, digits_N):
                N_list[n] = 9
        return int(''.join(map(str, N_list)))

暴走的楚狂

东八,好长时间没做题,做得太慢了😭