C语言重构【738】单调递增的数字

刺骨的言语ヽ痛彻心扉 2022-12-28 07:14 147阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
    
    （当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
    
    示例 1:
    
    输入: N = 10
    输出: 9
    示例 2:
    
    输入: N = 1234
    输出: 1234
    示例 3:
    
    输入: N = 332
    输出: 299
    说明: N 是在 [0, 10^9] 范围内的一个整数。```
    
    
    #### 方案：
    
    
    ```java
    using namespace ::std;
    class Solution
    { 
    public:
        int monotoneIncreasingDigits(int N)
        { 
            vector<int> res;
            //1.高位先取，如果满足递增则一直去下去
            //2.如果不满足，那么上一位--
            // 3.如果上一位-- 后，依然满足递增，则后面全9即可
            // 4.如果不满足，再上一位--，循环判断，直到最高位
            string digit = to_string(N);
            int len = digit.size();
            if (len < 2)
                return N;
            int i = 1;
            int flag = 0;
            while (i > 0 && i < len)
            { 
                if (digit[i] >= digit[i - 1])
                { 
                    //如果是调整过且符合要求，直接break
                    if (flag == 1)
                        break;
                    //如果没调整，那就老老实实i++
                    i++;
                }
                else if (digit[i] < digit[i - 1])
                { 
                    //上一位--，且调整标志置为1，一旦通过就通过
                    digit[--i]--;
                    flag = 1;
                }
            }
            //剩下的位全部置为9即可
            for (i; i < len - 1; i++)
            { 
                digit[i + 1] = '9';
            }
            return stoi(digit);
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode