貪心算法 一、738.單調(diào)遞增的數(shù)字 題目：

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

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：域名注冊、網(wǎng)站空間、營銷軟件、網(wǎng)站建設、遂寧網(wǎng)站維護、網(wǎng)站推廣。

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

示例 1:

• 輸入: N = 10
• 輸出: 9

示例 2:

• 輸入: N = 1234
• 輸出: 1234

示例 3:

• 輸入: N = 332
• 輸出: 299

說明: N?是在?[0, 10^9]?范圍內(nèi)的一個整數(shù)。

思路：

1、例如：98，一旦出現(xiàn)strNum[i - 1] >strNum[i]的情況（非單調(diào)遞增），首先想讓strNum[i - 1]--，然后strNum[i]給為9，這樣這個整數(shù)就是89，即小于98的大的單調(diào)遞增整數(shù)。

2、局部最優(yōu)：遇到strNum[i - 1] >strNum[i]的情況，讓strNum[i - 1]--，然后strNum[i]給為9，可以保證這兩位變成大單調(diào)遞增整數(shù)。

全局最優(yōu)：得到小于等于N的大單調(diào)遞增的整數(shù)。

但這里局部最優(yōu)推出全局最優(yōu)，還需要其他條件，即遍歷順序，和標記從哪一位開始統(tǒng)一改成9。

3、此時是從前向后遍歷還是從后向前遍歷呢？

從前向后遍歷的話，遇到strNum[i - 1] >strNum[i]的情況，讓strNum[i - 1]減一，但此時如果strNum[i - 1]減一了，可能又小于strNum[i - 2]。

這么說有點抽象，舉個例子，數(shù)字：332，從前向后遍歷的話，那么就把變成了329，此時2又小于了第一位的3了，真正的結果應該是299。

所以從前后向遍歷會改變已經(jīng)遍歷過的結果！

那么從后向前遍歷，就可以重復利用上次比較得出的結果了，從后向前遍歷332的數(shù)值變化為：332 ->329 ->299

確定了遍歷順序之后，那么此時局部最優(yōu)就可以推出全局。

//版本1
class Solution {
    public int monotoneIncreasingDigits(int N) {
        String[] strings = (N + "").split("");
        int start = strings.length;
        for (int i = strings.length - 1; i >0; i--) {
            if (Integer.parseInt(strings[i])< Integer.parseInt(strings[i - 1])) {
                strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                start = i;
            }
        }
        for (int i = start; i< strings.length; i++) {
            strings[i] = "9";
        }
        return Integer.parseInt(String.join("",strings));
    }
}

java版本1中創(chuàng)建了String數(shù)組，多次使用Integer.parseInt了方法，這導致不管是耗時還是空間占用都非常高，用時12ms，下面提供一個版本在char數(shù)組上原地修改，用時1ms的版本

//版本2
class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] >chars[i + 1]) {
                chars[i]--;
                start = i+1;
            }
        }
        for (int i = start; i< s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

二、總結

/file/tupian/20230121/貪心總結water.jpg

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當前名稱：代碼隨想錄算法訓練營第三十七天|738.單調(diào)遞增的數(shù)字總結-創(chuàng)新互聯(lián)
新聞來源：http://weahome.cn/article/csgecj.html