LeetCode 556. 下一个更大元素 III

约 5 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 字节 美团 猿辅导
标签
字符串 数学 双指针

题目描述

✅ 556. 下一个更大元素 III

image-20260928202455358

题意分析

重新排列正整数 n 的全部十进制数位，找出严格大于 n 的最小整数。每个数位的使用次数必须保持不变，不能新增或删除数位。

“更大”与“最小”要同时满足：原数本身不算答案，任意一个更大的排列也不一定是答案。不存在更大排列，或最小的更大排列超过 32 位有符号整数上限时，都返回 -1。

解法：下一排列

核心思路

[!blue]

数位数相同时，两个整数的大小由从左到右第一个不同的数位决定。因此，要让结果刚好变大，应尽量保留高位，把必须增大的位置推到最右侧。

从右向左找到第一个满足 digits[pivot] < digits[pivot + 1] 的位置。它右边的后缀已经是非递增排列，也就是这些数位能组成的最大排列；只调整后缀不可能让原数变大，所以必须增大 pivot。若找不到该位置，整个数已经是最大排列，直接返回 -1。

确定位置后，还要让这一位增加得尽量少。后缀非递增，从右向左找到的第一个严格大于 digits[pivot] 的数位，就是最小的可用替代值。交换后，后缀仍然非递增：交换位置右侧的数位都不大于旧的枢轴值，因此放回旧值不会破坏顺序。

最后反转后缀，把它变成非递减排列，也就是新高位确定后的最小后缀。这样依次保证“增大位置最靠右、该位增幅最小、剩余部分最小”，得到的正是下一个更大排列。先按 64 位整数解析，再检查 32 位上限，避免范围判断之前就发生溢出。

解题步骤

  1. 将 n 转为字符数组，从倒数第二位向左寻找 digits[pivot] < digits[pivot + 1]。
  2. 若 pivot < 0，说明全部数位非递增，没有更大排列，返回 -1。
  3. 从末位向左找第一个严格大于枢轴的数位，与枢轴交换。
  4. 反转 [pivot + 1, end]，使这个后缀按非递减顺序排列。
  5. 将结果解析成 64 位整数；超过 $2^{31}-1$ 时返回 -1，否则返回该整数。

代码实现

class Solution {
    public int nextGreaterElement(int n) {
        char[] digits = String.valueOf(n).toCharArray();

        int pivot = digits.length - 2;

        while (pivot >= 0 && digits[pivot] >= digits[pivot + 1]) {
            pivot--;
        }

        if (pivot < 0) {
            return -1;
        }

        // 后缀非递增，从右找第一个更大值，才能使高位增幅最小。
        int successor = digits.length - 1;

        while (digits[successor] <= digits[pivot]) {
            successor--;
        }

        swap(digits, pivot, successor);
        // 高位提升后，把后缀恢复为最小排列。
        reverse(digits, pivot + 1, digits.length - 1);

        long value = Long.parseLong(new String(digits));

        return value > Integer.MAX_VALUE ? -1 : (int) value;
    }

    private void reverse(char[] digits, int left, int right) {
        while (left < right) {
            swap(digits, left++, right--);
        }
    }

    private void swap(char[] digits, int i, int j) {
        char temp = digits[i];

        digits[i] = digits[j];
        digits[j] = temp;
    }
}

import "strconv"

func nextGreaterElement(n int) int {
    digits := []byte(strconv.Itoa(n))

    pivot := len(digits) - 2
    for pivot >= 0 && digits[pivot] >= digits[pivot+1] {
        pivot--
    }
    if pivot < 0 {
        return -1
    }

    // 后缀非递增，从右找第一个更大值，才能使高位增幅最小。
    successor := len(digits) - 1
    for digits[successor] <= digits[pivot] {
        successor--
    }
    digits[pivot], digits[successor] = digits[successor], digits[pivot]
    // 高位提升后，把后缀恢复为最小排列。
    for left, right := pivot+1, len(digits)-1; left < right; left, right = left+1, right-1 {
        digits[left], digits[right] = digits[right], digits[left]
    }

    value, _ := strconv.ParseInt(string(digits), 10, 64)
    if value > 1<<31-1 {
        return -1
    }
    return int(value)
}

复杂度分析

  • 时间复杂度：$O(d)$，其中 $d$ 是十进制数位数。寻找枢轴、寻找交换对象、反转和解析各扫描至多数位一次。
  • 空间复杂度：$O(d)$，用于字符数组和转换后的字符串；交换与反转本身只用常数空间。

关键点总结

[!green]

  • 最长非递增后缀无法通过内部重排变大，它前面的数位才是最靠右的可增大位置。
  • 从后缀右端找第一个更大数位，保证枢轴只增加必要的最小幅度。
  • 交换后后缀仍非递增，反转即可得到最小后缀，无需额外排序。
  • 数位重排可能突破整数上限；恰好等于上限仍是合法结果。

易错点总结

[!yellow]

  • 寻找枢轴时必须跳过大于或等于后一位的位置。相等不构成上升关系，不能作为增大入口。
  • 交换对象必须严格大于枢轴，且在后缀中尽量小；随意选择更大数位会跳过真正的下一排列。
  • 交换后不反转后缀，只能保证结果变大，不能保证它最小。
  • 无枢轴时必须先返回，不能继续用负下标访问数组，也不能像循环排列问题那样返回最小排列。
  • 先转为 32 位整数再判断范围，已经来不及防止溢出；应使用 64 位中间值，并用 > 而非 >= 判断上限。

相似题目

题目 难度 关联与区别
31. 下一个排列 中等 把整数各位当作数组后，直接寻找下一字典序排列，再检查结果是否超出整数范围。
7. 整数反转 中等 同样在十进制重组时注意32位边界，原题反转全部数位，本题只求最接近的更大重排。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/31938115
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！