c++ 6ms Backtracking


  • 0
    F
    bool dfs(string &s, int idx, string &pre)
    {
        if(idx == s.size()) return true;
        char maxDigit = s[idx];
        char minDigit = '0';
        if(idx > 0) {
            minDigit = pre[idx-1];
            for(int k = idx-1; k >=0; --k) {
                if(pre[k] < s[k]) {
                    maxDigit = '9';
                    break;
                }
            }
        }
    
        for(char d = maxDigit; d >= minDigit; --d) {
            pre.push_back(d);
            if(dfs(s, idx+1, pre)) return true;
            pre.pop_back();
        }
        return false;
    }
    
    int monotoneIncreasingDigits(int N) {
        string s = to_string(N);
        string sAns;
        dfs(s, 0, sAns);
        return stol(sAns);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.