Leetcode 738 单调递增的数字

2023-12-28 12:12:45

题意理解

? ? ? ? 即给定一个整数N,要求返回一个小等于N的数。

? ? ? ? 且从左到右,数字成递增排列,即满足x1<=x2。

? ? ? ? 如:????????n = 332????????输出: 299

????????如:????????n = 1234? ? ? ? 输出: 1234

解题思路

? ? ? ? 从两个角度考虑,从左到右确定这个目标数,还是从右到左确定这个目标数。

? ? ? ? 1.从左到右考虑,332,i=0,1时,符合递增,但i=2时,不符合递增,且取不到>=3的值

? ? ? ? 2.从右到左考虑,332,i=2时,取到2,2会限制前面取到很小的数字,将向下调整

? ? ? ? ? ? ? ? i=2时,取数字9,i=1,时做-1, 则有? ? ? ? 329,此时29满足条件。

? ? ? ? ? i=1时,取到数字2时,会限制前面取很小的数字,则将数字向下调整

? ? ? ? ? ? ? ? i=1时,取数字9,i=0,时做-1,则有????????299,此时299满足调整,切实最大的满足条件的值。

? ? ? ??

? ? ? ? 采用贪心思路解题,全局最优解:满足条件的最大值

? ? ? ? 局部最优解,为了使高位取到尽可能大的值,地位要给出能取到的最大值。

1.贪心解题

public int monotoneIncreasingDigits(int n) {
        char[] sNum=String.valueOf(n).toCharArray();
        //设置从哪个节点开始设置9
        int flag=sNum.length;
        for(int i=sNum.length-1;i>0;i--){
            if(sNum[i]<sNum[i-1]){
                flag=i;
                sNum[i-1]--;
            }
        }
        for(int i=flag;i<sNum.length;i++){
            sNum[i]='9';
        }
        return Integer.parseInt(String.valueOf(sNum));
    }

2.分析

时间复杂度:O(n) 遍历满足条件的数的时间

空间复杂度:O(n) 保存结果所需的空间。

n为输入数的位数。

先确定末尾数,再逐步确定前面的数。

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135255672
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。