556. Next Greater Element III
1. Description
Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.
Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.
2. Example
Example 1:
Input: n = 12
Output: 21
Example 2:
Input: n = 21
Output: -1
3. Constraints
- 1 <= n <= $2^{31} - 1$
4. Solutions
Math
n
Time complexity: O(logn)
Space complexity: O(logn)
// next permutation
// the space complexity is logn, but at most 32, I don't think it's reasonable to save the memory
class Solution {
public:
int nextGreaterElement(int n) {
string num_str = to_string(n);
int last_reverse_index = 0;
for (int i = num_str.size() - 1; i > 0; --i) {
if (num_str[i] > num_str[i - 1]) {
last_reverse_index = i;
break;
}
}
if (last_reverse_index == 0) {
return -1;
} else {
int index_to_swap = last_reverse_index - 1;
int least_num_to_swap_index = last_reverse_index;
for (int i = last_reverse_index; i < num_str.size(); ++i) {
if (num_str[i] > num_str[index_to_swap] &&
num_str[i] <= num_str[least_num_to_swap_index]) {
least_num_to_swap_index = i;
}
}
swap(num_str[index_to_swap], num_str[least_num_to_swap_index]);
reverse(num_str.begin() + last_reverse_index, num_str.end());
}
long result = stol(num_str);
return result > INT_MAX ? -1 : result;
}
};