Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
Example 1:
Input: 12 Output: 21
Example 2:
Input: 21 Output: -1
Related Topics:
String
Similar Questions:
// OJ: https://leetcode.com/problems/next-greater-element-iii/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
int nextGreaterElement(int n) {
auto s = to_string(n);
for (int i = s.size() - 2; i >= 0; --i) {
if (s[i] >= s[i + 1]) continue;
int j = lower_bound(s.begin() + i + 1, s.end(), s[i], greater<int>()) - s.begin() - 1;
swap(s[i], s[j]);
sort(s.begin() + i + 1, s.end());
long n = stol(s);
return n > INT_MAX ? -1 : n;
}
return -1;
}
};// OJ: https://leetcode.com/problems/next-greater-element-iii
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/85740/c-4-lines-next_permutation
class Solution {
public:
int nextGreaterElement(int n) {
auto digits = to_string(n);
next_permutation(begin(digits), end(digits));
auto ans = stol(digits);
return (ans > INT_MAX || ans <= n) ? -1 : ans;
}
};