738. Monotone Increasing Digits¶
Edited by Charles
Medium · Python · Greedy
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
The logic is once the right digit ‘r’ is less than the left digit ‘l’, change them locally to digits ‘(l - 1)9’. There pops up a problem. Take 332 as an example. If we iterate digits from left to right. For digits ‘33’, we do nothing; for digits ‘32’, we update it to ‘29’. Thus, iteration from left to right does not work properly since it sometimes sabotages the well-adjusted-and-iterated digit pairs.
Original study notes follow, including intermediate snippets and earlier attempts.
Note:
- The logic is once the right digit ‘r’ is less than the left digit ‘l’, change them locally to digits ‘(l - 1)9’.
- There pops up a problem. Take 332 as an example. If we iterate digits from left to right. For digits ‘33’, we do nothing; for digits ‘32’, we update it to ‘29’. Thus, iteration from left to right does not work properly since it sometimes sabotages the well-adjusted-and-iterated digit pairs.
- Then, the iteration from right to left would solve this concern. Once the pair is done, reconstruct the whole digit string by concatenation.
- Attention: we cannot assign characters to a string to make an update, since it is not allowed in Python.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | January 30, 2026 |
Python solution¶
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
s = str(n)
l = len(s)
for i in range(l - 1, 0, -1):
if s[i - 1] > s[i]:
s = s[: i - 1] + str(int(s[i - 1]) - 1) + '9' * (l - i)
return int(s)