Next Greater Element III Problem
Description
LeetCode Problem 556.
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.
Example 1:
1
2
Input: n = 12
Output: 21
Example 2:
1
2
Input: n = 21
Output: -1
Constraints:
- 1 <= n <= 2^31 - 1
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool nextPermutation(string& nums) {
int i = nums.size()-1;
while (i > 0 && nums[i-1] >= nums[i]) i--;
if (i == 0) return false;
int j = nums.size()-1;
while (j > 0 && nums[j] <= nums[i-1]) j--;
swap(nums[j], nums[i-1]);
reverse(nums.begin()+i, nums.end());
return true;
}
int nextGreaterElement(int n) {
string num = to_string(n);
bool res = nextPermutation(num);
size_t ans = stoll(num);
return (!res || ans > INT_MAX) ? -1 : ans;
}
};