题目ref{:target=”_blank”}
c++ next_permutation 的实现
1. 从后向前遍历,找到第一个逆序对(k-1,k)
2. 找到 k-1 位置后面 第一个 比 num[k-1] 大的位置 j
3. swap(nums[k-1], nums[j])
4. 将 [k, end) 按照从小到大排序,因为这里 [k, end) 是降序,所以直接reverse即可
5. 注意 数字没有next、和next溢出 INT_MAX 这两种情况
C++ 代码
手动实现
class Solution {
public:
int nextGreaterElement(int num) {
string s = to_string(num);
int n = s.size();
int k = n-1;
while(k && s[k] <= s[k-1])k--;
// 原数字最大,无next
if(!k)return -1;
// 找到第一个待交换的数字
int first = k - 1;
int second = n-1;
// 找到第二个待交换的数字,即第一个大于 s[first] 的数字
while(second>first && s[second] <= s[first])second--;
swap(s[first], s[second]);
// 后序数字从小达到排列
reverse(s.begin()+k, s.end());
long long res = stoll(s);
// INT 溢出判断
if(res > INT_MAX)return -1;
return res;
}
};
c++ next_permutation 使用,
bool ret = next_permutation(nums.begin(), nums.end()); 返回值表示是否能找到下一个排序
class Solution {
public:
int nextGreaterElement(int n) {
vector<int> nums;
while(n) {
nums.push_back(n%10);
n /= 10;
}
reverse(nums.begin(), nums.end());
bool ret = next_permutation(nums.begin(), nums.end());
if(!ret)return -1;
long res = 0;
for(int i : nums) {
res = res*10 + i;
}
if(res>INT_MAX)return -1;
return res;
}
};