Straightforward C++ O(n) solution


  • 0
    J

    The idea is very simple, scan from right to left, keep track of current maximum digit, and compare it to the one left adjacent to our scanned range. As long as current maximum is bigger, record them. If no swap needed, the i,j would remain initial value {-1,-1}

    int maximumSwap(int num) {
            string s = to_string(num);
            int n = s.size();
            if(n <= 1) return num;
            int i = -1, j = -1, cur = n-1, tmp = s[cur] - '0', res;
            for(int index = n-1; index > 0; index--){
                if(s[index] - '0' > tmp){   // update max
                    cur = index;
                    tmp = s[cur] - '0';
                }
                if(tmp > s[index-1] - '0'){// update i, j
                    i = cur;
                    j = index-1;
                }
            }
            if(i >= 0 && j >= 0) swap(s[i],s[j]);
            stringstream ss(s);
            ss >> res;
            return res;
        }
    

    Total running time 3ms for 111 test cases


Log in to reply
 

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