Create monotone_increasing_digits.py

yingl · web-flow · commit d5e635e94807 · 2018-04-03T13:50:42.000+08:00
diff --git a/monotone_increasing_digits.py b/monotone_increasing_digits.py
@@ -0,0 +1,20 @@
+from functools import reduce
+
+class Solution:
+    """
+    @param num: a non-negative integer N
+    @return: the largest number that is less than or equal to N with monotone increasing digits.
+    """
+    def monotoneDigits(self, num):
+        # write your code here
+        digits = list(map(int, list(str(num))))
+        digits_len = len(digits)
+        j = digits_len
+        for i in range(digits_len - 1, 0, -1):
+            if digits[i] > digits[i - 1]:
+                continue
+            digits[i - 1] -= 1
+            j = i
+        for i in range(j, digits_len):
+            digits[i] = 9
+        return reduce(lambda x, y: x * 10 + y, digits)
