LeetCode 题解工作台
下一个更大元素 III
给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。 注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。 示例 1： 输入： n = 12 …
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
class Solution: def nextGreaterElement(self, n: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。
注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。
示例 1：
输入：n = 12 输出：21
示例 2：
输入：n = 21 输出：-1
提示：
1 <= n <= 231 - 1
解题思路
方法一：双指针
class Solution:
def nextGreaterElement(self, n: int) -> int:
cs = list(str(n))
n = len(cs)
i, j = n - 2, n - 1
while i >= 0 and cs[i] >= cs[i + 1]:
i -= 1
if i < 0:
return -1
while cs[i] >= cs[j]:
j -= 1
cs[i], cs[j] = cs[j], cs[i]
cs[i + 1 :] = cs[i + 1 :][::-1]
ans = int(''.join(cs))
return -1 if ans > 2**31 - 1 else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(k) where k is the number of digits in n due to single pass scans for pivot, swap, and reverse. Space complexity is O(k) for digit storage when performing swaps and reversals. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect clear explanation of pivot selection and suffix reversal.
- question_mark
Look for careful handling of integer overflow with 32-bit constraints.
- question_mark
Candidate should articulate why two-pointer scanning ensures minimal increase.
常见陷阱
外企场景- error
Failing to scan from the right and missing the correct pivot location.
- error
Swapping with a digit that does not yield the minimal next number.
- error
Ignoring 32-bit integer constraints leading to incorrect return values.
进阶变体
外企场景- arrow_right_alt
Next Greater Element II with circular array considerations.
- arrow_right_alt
Next smaller permutation of digits problem using similar two-pointer logic.
- arrow_right_alt
Handling inputs with repeated digits requiring careful pivot and swap selection.