0556. Next Greater Element III
==============================
题目信息
--------
:题号: 0556
:难度: Medium
:主题: 十进制数字、相同数字重排、下一个更大值、32 位范围
:原题: `LeetCode 0556 `_
:重点: 必须使用原数的全部数字且次数不变、返回最小的更大整数、无答案或溢出时返回 -1
题目重述
--------
给定正整数 ``n``,重新排列它的十进制数字,寻找一个严格大于 ``n`` 的 32 位有符号整数。所有数字必须全部使用,并且每个数字的出现次数保持不变。
在所有满足条件的整数中返回最小者。若无法通过重排得到更大的整数,或者最小可行结果超过 ``2^31 - 1``,返回 ``-1``。结果不能因为重排产生无效的前导零。
自建示例
--------
存在下一个更大排列:
.. code-block:: text
输入:n = 218765
输出:251678
解释:251678 使用相同数字,并且是所有大于 218765 的重排结果中最小的一个。
数字已按降序排列:
.. code-block:: text
输入:n = 987
输出:-1
解释:任意其他排列都会小于 987,因此不存在更大结果。
对数字串执行下一排列
--------------------
要得到刚好更大的排列,从右向左找第一个下降位置 ``pivot``,再从末尾找到刚好大于 ``digits[pivot]`` 的数字交换,最后把后缀升序排列。若不存在下降位置,原数字已是最大排列;用 ``long long`` 解析结果后再检查 32 位上界。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int nextGreaterElement(int n) {
std::string digits = std::to_string(n);
int pivot = static_cast(digits.size()) - 2;
while (pivot >= 0 && digits[pivot] >= digits[pivot + 1]) {
--pivot;
}
if (pivot < 0) return -1;
int greater = static_cast(digits.size()) - 1;
while (digits[greater] <= digits[pivot]) --greater;
std::swap(digits[pivot], digits[greater]);
std::reverse(digits.begin() + pivot + 1, digits.end());
long long value = std::stoll(digits);
return value > INT_MAX ? -1 : static_cast(value);
}
};
代码分析
--------
后缀原本按非递增排列,交换后将它升序能使结果在所有更大排列中最小;没有枢轴则不存在更大排列。所有数字只重排不增删,时间复杂度为 ``O(d)``,额外空间复杂度为 ``O(d)``,其中 ``d`` 为位数。