下一个更大元素 III

556. 下一个更大元素 III

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

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

示例 1：

输入：n = 12
输出：21

示例 2：

输入：n = 21
输出：-1

提示：

1 <= n <= 2³¹ - 1

相似题目

下一个更大元素 I

下一个更大元素 II

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int nextGreaterElement(int n) { } };

java 解法, 执行用时: 0 ms, 内存消耗: 38.3 MB, 提交时间: 2023-06-12 15:48:13

class Solution {
    public int nextGreaterElement(int n) {
        int x = n, cnt = 1;
        for (; x >= 10 && x / 10 % 10 >= x % 10; x /= 10) {
            ++cnt;
        }
        x /= 10;
        if (x == 0) {
            return -1;
        }

        int targetDigit = x % 10;
        int x2 = n, cnt2 = 0;
        for (; x2 % 10 <= targetDigit; x2 /= 10) {
            ++cnt2;
        }
        x += x2 % 10 - targetDigit; // 把 x2 % 10 换到 targetDigit 上

        for (int i = 0; i < cnt; ++i, n /= 10) { // 反转 n 末尾的 cnt 个数字拼到 x 后
            int d = i != cnt2 ? n % 10 : targetDigit;
            if (x > Integer.MAX_VALUE / 10 || x == Integer.MAX_VALUE / 10 && d > 7) {
                return -1;
            }
            x = x * 10 + d;
        }
        return x;
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-12 15:47:53

func nextGreaterElement(n int) int {
    x, cnt := n, 1
    for ; x >= 10 && x/10%10 >= x%10; x /= 10 {
        cnt++
    }
    x /= 10
    if x == 0 {
        return -1
    }

    targetDigit := x % 10
    x2, cnt2 := n, 0
    for ; x2%10 <= targetDigit; x2 /= 10 {
        cnt2++
    }
    x += x2%10 - targetDigit // 把 x2%10 换到 targetDigit 上

    for i := 0; i < cnt; i++ { // 反转 n 末尾的 cnt 个数字拼到 x 后
        d := targetDigit
        if i != cnt2 {
            d = n % 10
        }
        if x > math.MaxInt32/10 || x == math.MaxInt32/10 && d > 7 {
            return -1
        }
        x = x*10 + d
        n /= 10
    }
    return x
}

python3 解法, 执行用时: 44 ms, 内存消耗: 15.8 MB, 提交时间: 2023-06-12 15:47:31

# 数学方法，从n开始，不断比较其最低位数字和次低位数字的大小，
# 如果次低位数字不低于最低位数字，则移除最低位数字，继续循环
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        x, cnt = n, 1
        while x >= 10 and x // 10 % 10 >= x % 10:
            cnt += 1
            x //= 10
        x //= 10
        if x == 0:
            return -1

        targetDigit = x % 10
        x2, cnt2 = n, 0
        while x2 % 10 <= targetDigit:
            cnt2 += 1
            x2 //= 10
        x += x2 % 10 - targetDigit  # 把 x2 % 10 换到 targetDigit 上

        MAX_INT = 2 ** 31 - 1
        for i in range(cnt):  # 反转 n 末尾的 cnt 个数字拼到 x 后
            d = n % 10 if i != cnt2 else targetDigit
            # 为了演示算法，请读者把 x 视作一个 32 位有符号整数
            if x > MAX_INT // 10 or x == MAX_INT // 10 and d > 7:
                return -1
            x = x * 10 + d
            n //= 10
        return x

javascript 解法, 执行用时: 52 ms, 内存消耗: 41.1 MB, 提交时间: 2023-06-12 15:46:21

/**
 * @param {number} n
 * @return {number}
 */
const MAX = 2147483647;
var nextGreaterElement = function(n) {
    const nums = [...('' + n)];
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i < 0) {
        return -1;
    }

    let j = nums.length - 1;
    while (j >= 0 && nums[i] >= nums[j]) {
        j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
    reverse(nums, i + 1);
    const ans = 0 + nums.join('');
    return ans > MAX ? -1 : ans;
};

const reverse = (nums, begin) => {
    let i = begin, j = nums.length - 1;
    while (i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
        j--;
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-12 15:46:02

func nextGreaterElement(n int) int {
    nums := []byte(strconv.Itoa(n))
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    if i < 0 {
        return -1
    }

    j := len(nums) - 1
    for j >= 0 && nums[i] >= nums[j] {
        j--
    }
    nums[i], nums[j] = nums[j], nums[i]
    reverse(nums[i+1:])
    ans, _ := strconv.Atoi(string(nums))
    if ans > math.MaxInt32 {
        return -1
    }
    return ans
}

func reverse(a []byte) {
    for i, n := 0, len(a); i < n/2; i++ {
        a[i], a[n-1-i] = a[n-1-i], a[i]
    }
}

java 解法, 执行用时: 0 ms, 内存消耗: 38.3 MB, 提交时间: 2023-06-12 15:45:46

class Solution {
    public int nextGreaterElement(int n) {
        char[] nums = Integer.toString(n).toCharArray();
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i < 0) {
            return -1;
        }

        int j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1);
        long ans = Long.parseLong(new String(nums));
        return ans > Integer.MAX_VALUE ? -1 : (int) ans;
    }

    public void reverse(char[] nums, int begin) {
        int i = begin, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    public void swap(char[] nums, int i, int j) {
        char temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

python3 解法, 执行用时: 32 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-12 15:45:33

'''
下一个排列
'''
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        nums = list(str(n))
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i < 0:
            return -1

        j = len(nums) - 1
        while j >= 0 and nums[i] >= nums[j]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = nums[i + 1:][::-1]
        ans = int(''.join(nums))
        return ans if ans < 2 ** 31 else -1

上一题

下一题

详情