Formatted question description: https://leetcode.ca/all/556.html
556. Next Greater Element III (Medium)
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:
Solution 1.
// OJ: https://leetcode.com/problems/next-greater-element-iii/
// 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;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/next-greater-element-iii
// 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;
}
};
Java
-
class Solution { public int nextGreaterElement(int n) { char[] array = String.valueOf(n).toCharArray(); boolean next = nextPermutation(array); if (!next) return -1; String nextGreaterElementStr = new String(array); long nextGreaterElementLong = Long.parseLong(nextGreaterElementStr); if (nextGreaterElementLong > Integer.MAX_VALUE) return -1; else { int nextGreaterElement = (int) nextGreaterElementLong; return nextGreaterElement; } } public boolean nextPermutation(char[] array) { int length = array.length; int index = -1; char curChar = Character.MAX_VALUE; for (int i = length - 1; i > 0; i--) { int difference = array[i] - array[i - 1]; if (difference > 0) { index = i - 1; curChar = array[i - 1]; break; } } if (index < 0) { Arrays.sort(array); return false; } int nextIndex = -1; char nextChar = Character.MAX_VALUE; for (int i = index + 1; i < length; i++) { if (array[i] > curChar && array[i] < nextChar) { nextIndex = i; nextChar = array[i]; } } array[index] = nextChar; array[nextIndex] = curChar; Arrays.sort(array, index + 1, length); return true; } }
-
// OJ: https://leetcode.com/problems/next-greater-element-iii/ // 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; } };
-
class Solution(object): def nextGreaterElement(self, n): """ :type n: int :rtype: int """ num = n n = list(str(n)) pos = leftMost = len(n) - 1 for i in reversed(range(0, len(n) - 1)): if n[i] < n[i + 1]: leftMost = i break for i in reversed(range(leftMost + 1, len(n))): if n[i] > n[leftMost]: pos = i break n[leftMost], n[pos] = n[pos], n[leftMost] n[leftMost + 1:] = sorted(n[leftMost + 1:]) n = int("".join(n)) print n if n <= num or n > 0x7fffffff: return -1 return n