給定一個非負整數?N，找出小于或等于?N?的最大的整數，同時這個整數需要滿足其各個位數上的數字是單調遞增。

（當且僅當每個相鄰位數上的數字?x?和?y?滿足?x <= y?時，我們稱這個整數是單調遞增的。）

示例 1:

輸入: N = 10
輸出: 9
示例 2:

輸入: N = 1234
輸出: 1234
示例 3:

輸入: N = 332
輸出: 299
說明: N?是在?[0, 10^9]?范圍內的一個整數。

思路：

如果a[i]一直大于等于a[i-1]，直接輸出就好

如果不是，需要判斷，主要分兩種情況：

1.如果a[i]<a[i-1]并且a[i-1]>a[i-2]，則a[i-1]-=1，后面的都變為9

例如：123453->123449

2.如果a[i]<a[i-1]并且a[i-1]>=a[i-2],則一直向前遍歷，直到a[k]!=a[i-1]，然后a[k]-=1,h后面的都變為9

例如：123332->122999

提交的代碼：

class?Solution?{

????public?int?monotoneIncreasingDigits(int?N)?{

????????int?t,sum=0,i=0,n=1,b;

????????????int?a[]?=?new?int[12];

????????????t?=?N;

????????????while(t!=0)

????????????{

????????????????t?=?t/10;

????????????????i++;

????????????}

????????????t?=?N;

????????????b=i;

????????????while(t!=0)

????????????{

????????????????a[i-1]?=?t%10;

????????????????t?=?t/10;

????????????????i--;

????????????}

????????????t=0;

????????????sum?=?a[0];

????????????for(i?=0;i<b;i++)

????????????{

????????????????if(i>0)

????????????????{

????????????????????if(a[i]>=a[i-1])

????????????????????{

????????????????????????sum?=?sum*10+a[i];

????????????????????????if(a[i]==a[i-1])

????????????????????????{

????????????????????????????n++;? //n用來記錄有多少個連續相同的數字

????????????????????????}

????????????????????????else

????????????????????????{

????????????????????????????n=1;

????????????????????????}

????????????????????????continue;

????????????????????}

????????????????????else

????????????????????{

????????????????????????while(n!=0)

????????????????????????{

????????????????????????????sum?=?sum-a[i-1-t];

????????????????????????????sum?=?sum/10;

????????????????????????????t++;

????????????????????????????n--;

????????????????????????????//System.out.println(sum);

????????????????????????}

????????????????????????a[i-t]?=?a[i-t]?-?1;

????????????????????????sum?=?sum*10+a[i-t];

???????????????????????//?System.out.println(sum);

????????????????????????for(int?j=i-t+1;j<b;j++)

????????????????????????{

????????????????????????????a[j]?=?9;

????????????????????????????sum?=?sum*10+a[j];

????????????????????????}

????????????????????????break;

????????????????????}

????????????????}

????????????}

????????????return?sum;

????}

}

總結

以上是生活随笔為你收集整理的Leetcode--738. 单调递增的数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。