738. Monotone Increasing Digits

738. Monotone Increasing Digits

难度: Medium

刷题内容

原题连接

内容描述

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:
Input: N = 10
Output: 9
Example 2:
Input: N = 1234
Output: 1234
Example 3:
Input: N = 332
Output: 299
Note: N is an integer in the range [0, 10^9].

解题方案

思路 1
- 时间复杂度: O(D^2)- 空间复杂度: O(D)

贪心,从第一位数字开始构造,每次构造出最大的满足条件的prefix

beats 58.46%

```python
class Solution:
def monotoneIncreasingDigits(self, N):
"""
:type N: int
:rtype: int
"""
digits = []
A = list(map(int, str(N)))

top Created with Sketch.