Medium

题目描述

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意： 返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

示例 1：

输入：n = 12
输出：21

示例 2：

输入：n = 21
输出：-1

提示：

  • 1 <= n <= 2^31 - 1

解题思路

这道题本质上是求下一个更大的排列（Next Permutation）问题。我们需要找到当前数字的下一个字典序更大的排列。

解题思路：

  1. 从右向左找到第一个递减的位置：将数字转换为字符串，从右向左遍历，找到第一个满足 nums[i] < nums[i+1] 的位置 i。如果找不到这样的位置，说明当前排列已经是最大的，返回 -1。

  2. 找到要交换的元素：从右向左找到第一个大于 nums[i] 的元素位置 j，这是我们需要与 nums[i] 交换的元素。

  3. 交换并翻转：交换 nums[i] 和 nums[j]，然后将 i+1 位置之后的所有元素翻转，使其变成升序排列，这样就得到了下一个更大的排列。

  4. 边界检查：检查结果是否超出 32 位整数范围。

这个算法的核心思想是尽可能小地增加数字的值，通过交换和翻转操作实现最小的增量。

时间复杂度为 O(d)，空间复杂度为 O(d)，其中 d 是数字的位数。

代码实现

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        int len = s.length();
        
        // 从右向左找第一个递减的位置
        int i = len - 2;
        while (i >= 0 && s[i] >= s[i + 1]) {
            i--;
        }
        
        // 如果没找到，说明是最大排列
        if (i < 0) {
            return -1;
        }
        
        // 从右向左找第一个大于s[i]的元素
        int j = len - 1;
        while (s[j] <= s[i]) {
            j--;
        }
        
        // 交换
        swap(s[i], s[j]);
        
        // 翻转i+1之后的部分
        reverse(s.begin() + i + 1, s.end());
        
        // 检查是否超出32位整数范围
        long long result = stoll(s);
        if (result > INT_MAX) {
            return -1;
        }
        
        return (int)result;
    }
};

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        s = list(str(n))
        length = len(s)
        
        # 从右向左找第一个递减的位置
        i = length - 2
        while i >= 0 and s[i] >= s[i + 1]:
            i -= 1
        
        # 如果没找到，说明是最大排列
        if i < 0:
            return -1
        
        # 从右向左找第一个大于s[i]的元素
        j = length - 1
        while s[j] <= s[i]:
            j -= 1
        
        # 交换
        s[i], s[j] = s[j], s[i]
        
        # 翻转i+1之后的部分
        s[i + 1:] = reversed(s[i + 1:])
        
        # 检查是否超出32位整数范围
        result = int(''.join(s))
        if result > 2**31 - 1:
            return -1
        
        return result

public class Solution {
    public int NextGreaterElement(int n) {
        char[] chars = n.ToString().ToCharArray();
        int length = chars.Length;
        
        // 从右向左找第一个递减的位置
        int i = length - 2;
        while (i >= 0 && chars[i] >= chars[i + 1]) {
            i--;
        }
        
        // 如果没找到，说明是最大排列
        if (i < 0) {
            return -1;
        }
        
        // 从右向左找第一个大于chars[i]的元素
        int j = length - 1;
        while (chars[j] <= chars[i]) {
            j--;
        }
        
        // 交换
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        
        // 翻转i+1之后的部分
        Array.Reverse(chars, i + 1, length - i - 1);
        
        // 检查是否超出32位整数范围
        if (long.TryParse(new string(chars), out long result)) {
            if (result > int.MaxValue) {
                return -1;
            }
            return (int)result;
        }
        
        return -1;
    }
}

var nextGreaterElement = function(n) {
    let s = n.toString().split('');
    let length = s.length;
    
    // 从右向左找第一个递减的位置
    let i = length - 2;
    while (i >= 0 && s[i] >= s[i + 1]) {
        i--;
    }
    
    // 如果没找到，说明是最大排列
    if (i < 0) {
        return -1;
    }
    
    // 从右向左找第一个大于s[i]的元素
    let j = length - 1;
    while (s[j] <= s[i]) {
        j--;
    }
    
    // 交换
    [s[i], s[j]] = [s[j], s[i]];
    
    // 翻转i+1之后的部分
    let left = i + 1, right = length - 1;
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]];
        left++;
        right--;
    }
    
    // 检查是否超出32位整数范围
    let result = parseInt(s.join(''));
    if (result > Math.pow(2, 31) - 1) {
        return -1;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(d)，其中 d 是数字的位数。需要遍历数字的每一位进行查找、交换和翻转操作
空间复杂度O(d)，需要额外的字符串或数组空间来存储数字的每一位

相关题目