738

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].

Companies:
SAP

Related Topics:
Greedy

Similar Questions:

• Remove K Digits (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/monotone-increasing-digits/
// Author: github.com/lzl124631x
// Time: O(log_10^N)
// Space: O(log_10^N)
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        vector<int> v;
        while (n) {
            v.push_back(n % 10);
            n /= 10;
        }
        int i = v.size() - 2, ans = 0;
        for (; i >= 0 && v[i] >= v[i + 1]; --i);
        if (i >= 0) {
            while (i + 2 < v.size() && v[i + 1] == v[i + 2]) ++i;
            v[i + 1]--;
            while (i >= 0) v[i--] = 9;
        }
        while (v.size()) {
            ans = ans * 10 + v.back();
            v.pop_back();
        }
        return ans; 
    }
};