738. Monotone Increasing Digits

leetcode medium

#array#csharp#leetcode#medium#string

Task

Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами.

Пример:

Input: n = 10

Output: 9

C# solution

matched/original

public class Solution {
    public int MonotoneIncreasingDigits(int N) {
        var digits = N.ToString().ToCharArray();
        int marker = digits.Length;
        
        for (int i = digits.Length - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                marker = i;
                digits[i - 1]--;
            }
        }
        
        for (int i = marker; i < digits.Length; i++) {
            digits[i] = '9';
        }
        
        return int.Parse(new string(digits));
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MonotoneIncreasingDigits(int N) {
        var digits = N.ToString().ToCharArray();
        int marker = digits.size();
        
        for (int i = digits.size() - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                marker = i;
                digits[i - 1]--;
            }
        }
        
        for (int i = marker; i < digits.size(); i++) {
            digits[i] = '9';
        }
        
        return int.Parse(new string(digits));
    }
}

Java solution

matched/original

public class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] digits = Integer.toString(n).toCharArray();
        int mark = digits.length;

        for (int i = digits.length - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                mark = i;
                digits[i - 1]--;
            }
        }

        for (int i = mark; i < digits.length; i++) {
            digits[i] = '9';
        }

        return Integer.parseInt(new String(digits));
    }
}

JavaScript solution

matched/original

var monotoneIncreasingDigits = function(n) {
    let digits = Array.from(String(n), Number);
    let mark = digits.length;
    
    for (let i = digits.length - 1; i > 0; i--) {
        if (digits[i] < digits[i - 1]) {
            mark = i;
            digits[i - 1]--;
        }
    }
    
    for (let i = mark; i < digits.length; i++) {
        digits[i] = 9;
    }
    
    return parseInt(digits.join(''), 10);
};

Python solution

matched/original

def monotoneIncreasingDigits(n):
    digits = list(str(n))
    mark = len(digits)
    
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            mark = i
            digits[i - 1] = str(int(digits[i - 1]) - 1)
    
    for i in range(mark, len(digits)):
        digits[i] = '9'
    
    return int("".join(digits))

Go solution

matched/original

package main

import "strconv"

func monotoneIncreasingDigits(N int) int {
    digits := []byte(strconv.Itoa(N))
    marker := len(digits)
    
    for i := len(digits) - 1; i > 0; i-- {
        if digits[i] < digits[i-1] {
            marker = i
            digits[i-1]--
        }
    }
    
    for i := marker; i < len(digits); i++ {
        digits[i] = '9'
    }
    
    result, _ := strconv.Atoi(string(digits))
    return result
}

Explanation

Algorithm

Преобразуйте число в строку для удобства обработки.

Найдите позицию, где последовательность перестает быть монотонной.

Уменьшите соответствующую цифру и установите все последующие цифры в 9.

😎