Daily Leetcode 670. Maximum Swap

https://leetcode.com/problems/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]

题目分析：

这一题的目的是通过交换给定数字中的任意两个数，使得交换后的数最大。

我们将最右最大的数（数位较低）与最左最小的数（数位较高）交换，就能够保证得到一个最大的数。我们首先将最后一位数记为最右最大数，位置记为currentMaxPos，再从右向左遍历，若i位置上的数小于currentMaxPos，则当前交换对为(i, currentMaxPos)；若i位置上的数大于currentMaxPos，则currentMaxPos更新为i。遍历完成后，将位置i上的数与位置currentMaxPos上的数进行交换即可。

代码：

class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        
        tmpNum = list(str(num))
        currentMaxPos = len(tmpNum) - 1
        leftMin, rightMax = 0, 0
        
        for i in reversed(range(len(tmpNum))):
            if tmpNum[i] < tmpNum[currentMaxPos]:
                leftMin, rightMax = i, currentMaxPos
            elif tmpNum[i] > tmpNum[currentMaxPos]:
                currentMaxPos = i

        tmpNum[leftMin], tmpNum[rightMax] = tmpNum[rightMax], tmpNum[leftMin]
    
        return int("".join(tmpNum))