Maximum Swap

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: 9973
Output: 9973
Explanation: No swap.

Note:

1. The given number is in the range [0, 108]

class Solution {
public:
    int helper(vector<int> nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            ans = ans * 10 + nums[i];
        }
        return ans;
    }
    int maximumSwap(int num) {
        if (num == 0) {
            return num;
        }
        vector<int> temp;
        int tmp = num;
     
        while (tmp != 0) {
            int digit = tmp % 10;
            temp.insert(temp.begin(), digit);
            tmp = tmp / 10;
        }
        int start = 0;
        int i = start + 1;
        int max;
        while(i < temp.size()) {
            max = i;
            while (i < temp.size()) {
                if (temp[i] >= temp[max]) {
                    max = i;
                }
                i++;
            }
            if (i == temp.size()) {
                if (temp[max] > temp[start]) {
                    int swp = temp[start];
                    temp[start] = temp[max];
                    temp[max] = swp;
                    break;
                } else {
                    start++;
                    i = start + 1;
                }
            }
        }
        if (start == temp.size() - 1) {
            return num;
        }
        return helper(temp);
     
    }
};

============ Efficient ========
class Solution { public: int maximumSwap(int num) { int maxDigit = -1, maxIdx = -1; int leftIdx = -1, rightIdx = -1; string numStr = to_string(num); for(int i = numStr.size()-1; i>=0; i--) { if(numStr[i] > maxDigit) { maxDigit = numStr[i]; maxIdx = i; continue; } if(numStr[i] < maxDigit) { leftIdx = i; rightIdx = maxIdx; } } if(leftIdx == -1) return num; swap(numStr[leftIdx], numStr[rightIdx]); return stoi(numStr); } };