[LeetCode] 556. Next Greater Element III

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

下一个更大的元素III。

版本三其实跟前两个版本几乎没什么关系，是一道找next permutation的题。题意是给一个整数，请找出Integer范围内用到相同数字但是比当前数字大的数字。如果想看怎么跑例子可以参见我31题的题解。题干中给的例子不是很好，我这里给一个更长的例子。

198765432, 他的下一个更大的元素是213456789

首先排除一个corner case，如果input的digits是从左到右递减的，比如54321这种，他是没有更大的元素的，直接返回-1。那么一般的case是什么呢，比如198765432，他的下一个更大的元素是通过把最后一位的2先跟1交换，得到298765431，然后再把红色的部分整体reverse得到213456789。为什么是跟2交换是因为2是比1大的数字里面最小的那一个。

所以在写代码的时候，交换的原则是数字从右往左扫描，一般情况下会一直递增，当突然发现一个数字不再递增的时候就停下。停下的位置上的数字要跟数字最后一位交换，比如这个例子里的1和2，198765432。交换完了之后，因为1之后的部分都是递减的，所以需要整体翻转，以得到最后的那个数字。

时间O(n)

空间O(1) - 因为创建的数组最多只有32位，并不随着input变大

Java实现

 1 class Solution {
 2     public int nextGreaterElement(int n) {
 3         String number = String.valueOf(n);
 4         char[] res = number.toCharArray();
 5 
 6         int i = res.length - 2;
 7         while (i >= 0 && res[i + 1] <= res[i]) {
 8             i--;
 9         }
10         if (i < 0)
11             return -1;
12 
13         int j = res.length - 1;
14         while (j >= 0 && res[j] <= res[i]) {
15             j--;
16         }
17         swap(res, i, j);
18         reverse(res, i + 1);
19         long val = Long.parseLong(new String(res));
20         return val <= Integer.MAX_VALUE ? (int) val : -1;
21     }
22 
23     private void reverse(char[] chars, int start) {
24         int i = start;
25         int j = chars.length - 1;
26         while (i < j) {
27             swap(chars, i++, j--);
28         }
29     }
30 
31     private void swap(char[] chars, int i, int j) {
32         char temp = chars[i];
33         chars[i] = chars[j];
34         chars[j] = temp;
35     }
36 }