Skip to content

738. Monotone Increasing Digits 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int monotoneIncreasingDigits(int n) {
    string s = to_string(n);
    const int n = s.length();
    int k = n;  // s[k..n) -> '9'

    for (int i = n - 1; i > 0; --i)
      if (s[i] < s[i - 1]) {
        --s[i - 1];
        k = i;
      }

    for (int i = k; i < n; ++i)
      s[i] = '9';

    return stoi(s);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int monotoneIncreasingDigits(int n) {
    char[] s = String.valueOf(n).toCharArray();
    final int n = s.length;
    int k = n; // s[k..n) -> '9'

    for (int i = n - 1; i > 0; --i)
      if (s[i] < s[i - 1]) {
        --s[i - 1];
        k = i;
      }

    for (int i = k; i < n; ++i)
      s[i] = '9';

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