最大交换

分手后的思念是犯贱 2022-12-27 02:27 188阅读 0赞

> leetcode 670 \[medium\]  
> 中：[最大交换][Link 1]  
> 英：[Maximum Swap][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解 ###

##### 1. 思路 #####

1.  要使得交换后数最大，那么就要让当前数中的**未处于尽可能高位的最大的数字字符**交换到尽可能更高位  
    例如对于 `937` ，`9` 是最大数字字符，但已经**处于尽可能高位**，而 `7` 是当前**未处于尽可能高位的最大的数字字符**
2.  当满足 **“未处于尽可能高位的最大的数字字符”** 有多个时，要**尽量选择原本处以更低位**的  
    例如对于 `9377` ，我们选择交换 `个位的7` 而不是 `十位的7`

##### 2. 步骤（栈 + 贪心） #####

1.  从末尾遍历num各位，若当前元素比栈顶元素大(空栈直接入栈)，入栈。直到num头或者当前位为9。
2.  从起始遍历num各位，比较当前位于栈顶元素的大小和位置关系  
    （1）若当前元素比栈顶元素小，且满足当前元素在高位，栈顶元素在低位，则交换，返回结果；  
    （2）若不满足高低位关系，则栈顶元素出栈，继续比较；  
    （3）若栈为空，说明无需交换；

##### 3. 时间复杂度：O(n) #####

##### 4. 空间复杂度：O(1) 栈空间，最多只有10个元素 #####

##### 5. 实现 #####

/** * @param {number} num * @return {number} */
    var maximumSwap = function(num) { 
        // 预处理
        let numStr = num.toString();
        let numStrLen = numStr.length;
    
        // 构建stack, 从末尾开始遍历numStr各位，若当前元素比栈顶元素大，入栈。直到num头或者当前位为9
        let stack = [[numStr[numStrLen-1], numStrLen-1]];   // item: [char, idx]
        let stackTop = [numStr[numStrLen-1], numStrLen-1];
        for(let i=numStrLen-2; i>=0; i--){ 
            if(stackTop[0] === '9') break;
            if(numStr[i] > stackTop[0]) stack.push(stackTop = [numStr[i], i]);
        }
    
        // 从头开始遍历numStr各位
        for(let i=0; i<numStrLen; i++){ 
            if(stackTop[1] <= i) { 
                stackTop = stack.pop();
                if(!stackTop) break;
            }
            if(numStr[i] < stackTop[0]){ 
                // 交换，退出
                numStr = numStr.slice(0, i) + stackTop[0] + numStr.slice(i+1, stackTop[1]) + numStr[i] + numStr.slice(stackTop[1]+1);
                break;
            }
        }
    
        // 返回结果
        return Number(numStr);
    };

[Link 1]: https://leetcode-cn.com/problems/maximum-swap/
[Maximum Swap]: https://leetcode.com/problems/maximum-swap/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/c58790202c1e48348124bde1308f67d1.png