Description

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.

Solution

遍历三遍：
1.找累积最大值array(from left)
2.正向找第一个max_array[i]>num[i]的pos
3.交换pos和后面(倒序出现的第一个max的pos)

class Solution:
    def maximumSwap(self, num: int) -> int:
        num_old = num
        num = list(map(int,str(num)))
        n_max = [0]*len(num)
        n_max[-1] = 0 # last number should be zero
        for i in range(len(n_max)-2,-1,-1):
            if num[i+1]> n_max[i+1]:
                n_max[i]= num[i+1]
            else:
                n_max[i] = n_max[i+1]
        for i in range(len(n_max)):
            if n_max[i]>num[i]:
                break
        
        if i == len(n_max):
            return num_old
        for k in range(len(n_max)-1,-1,-1):
            if num[k] == n_max[i]:
                tmp = num[i]
                num[i]=num[k] 
                num[k] = tmp
                break
        ans = 0
        for n in num:
            ans*=10
            ans+=n
            
        return ans