TNotes.leetcode

Appearance

⏰0556. 下一个更大元素 III【中等】

0556. 下一个更大元素 III【中等】 ​

1. 📝 题目描述 ​

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

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

示例 1：

txt
输入：n = 12
输出：21

示例 2：

txt
输入：n = 21
输出：-1

提示：

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

2. 🎯 s.1 - 下一个排列 ​

c
int nextGreaterElement(int n) {
    char digits[12];
    sprintf(digits, "%d", n);
    int len = strlen(digits);
    int i = len - 2;
    while (i >= 0 && digits[i] >= digits[i + 1]) i--;
    if (i < 0) return -1;
    int j = len - 1;
    while (digits[j] <= digits[i]) j--;
    char tmp = digits[i]; digits[i] = digits[j]; digits[j] = tmp;
    int l = i + 1, r = len - 1;
    while (l < r) {
        tmp = digits[l]; digits[l] = digits[r]; digits[r] = tmp;
        l++; r--;
    }
    long long res = atoll(digits);
    return res > 2147483647 ? -1 : (int)res;
}
js
/**
 * @param {number} n
 * @return {number}
 */
var nextGreaterElement = function (n) {
  const digits = ('' + n).split('')
  const len = digits.length
  let i = len - 2
  while (i >= 0 && digits[i] >= digits[i + 1]) i--
  if (i < 0) return -1
  let j = len - 1
  while (digits[j] <= digits[i]) j--
  ;[digits[i], digits[j]] = [digits[j], digits[i]]
  let l = i + 1,
    r = len - 1
  while (l < r) {
    ;[digits[l], digits[r]] = [digits[r], digits[l]]
    l++
    r--
  }
  const res = parseInt(digits.join(''))
  return res > 2147483647 ? -1 : res
}
py
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = list(str(n))
        length = len(digits)
        i = length - 2
        while i >= 0 and digits[i] >= digits[i + 1]:
            i -= 1
        if i < 0:
            return -1
        j = length - 1
        while digits[j] <= digits[i]:
            j -= 1
        digits[i], digits[j] = digits[j], digits[i]
        digits[i + 1:] = reversed(digits[i + 1:])
        res = int(''.join(digits))
        return res if res <= 2**31 - 1 else -1
  • 时间复杂度：O(log⁡n)，即数字的位数
  • 空间复杂度：O(log⁡n)

算法思路：

  • 从右向左找第一个下降位置 i（digits[i] < digits[i+1]）
  • 从右向左找第一个大于 digits[i] 的位置 j，交换后反转 i+1 到末尾
  • 若结果超过 32 位有符号整数范围则返回 -1