leetcode-go/medium/670.maximum-swap.go

func maximumSwap(num int) int {
	digit := make([]int, 0)
	for i := num; 0 < i; i /= 10 {
		digit = append(digit, i%10)
	}
	n := len(digit)
	max := make([]int, n)
	for i := 1; i < n; i++ {
		max[i] = i // max[i]: the maximum digit that lower than the ith digit
		if digit[i] <= digit[max[i-1]] {
			max[i] = max[i-1]
		}
	}
	for i := n - 1; 0 <= i; i-- {
		if digit[i] < digit[max[i]] {
			digit[i], digit[max[i]] = digit[max[i]], digit[i]
			res := 0
			for j := n - 1; 0 <= j; j-- {
				res *= 10
				res += digit[j]
			}
			return res
		}
	}
	return num
}