給定一個非負整數(shù) N，找出小于或等于 N 的最大的整數(shù)，同時這個整數(shù)需要滿足其各個位數(shù)上的數(shù)字是單調(diào)遞增。
（當且僅當每個相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時，我們稱這個整數(shù)是單調(diào)遞增的。）

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

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

示例 3:
輸入: N = 332
輸出: 299
————————————————————————————————————————————————————————
這道題貪心算法思路就是：
局部最優(yōu)：遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]–，然后strNum[i]給為9，保證變成最大單調(diào)遞增
全局最優(yōu)：得到小于等于n的最大單調(diào)遞增函數(shù)

這里需要注意，遍歷要從個位開始，即從后向前遍歷，
還有這里str[i]變成9需要單獨整體操作，所以需要一個flag來標記9是從哪開始的
開始我就踩了這個坑，代碼是

class Solution { public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);for (int i = strNum.size() - 1; i > 0; --i) {if (strNum[i - 1] > strNum[i]) {strNum[i] = '9';strNum[i - 1]--;}}return stoi(strNum);} };

這樣就會在一些情況下出問題，如n為100時會輸出90，而實際上我們需要的是99；
正確代碼如下：

class Solution { public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);//這個初始化是防止第一個for循環(huán)沒有執(zhí)行的情況int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; --i) {if (strNum[i - 1] > strNum[i]) {flag = i;strNum[i - 1]--;}}for (int i = flag; i < strNum.size(); ++i) {strNum[i] = '9';}return stoi(strNum);} };

總結

以上是生活随笔為你收集整理的738. 单调递增的数字（贪心算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。