# LeetCode 556. Next Greater Element III

2021年09月15日 阅读数：5

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 nand is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.post

Example 1:url

```Input: 12
Output: 21```

Example 2:spa

```Input: 21
Output: -1```

"2", "3"换位, 变成"53421", 再把3后面的部分sort成从小到大 "53124"就是next greater element.ip

Time Complexity: O(x), x是n的digit 数目. 每一个digit不会走超过3遍.element

Space: O(x).

AC Java:

``` 1 class Solution {
2     public int nextGreaterElement(int n) {
3         char [] arr = (""+n).toCharArray();
4         int i = arr.length-2;
5         while(i>=0 && arr[i]>=arr[i+1]){
6             i--;
7         }
8
9         if(i < 0){
10             return -1;
11         }
12
13         int j = arr.length-1;
14         while(j>i && arr[j]<=arr[i]){
15             j--;
16         }
17
18         swap(arr, i, j);
19         reverse(arr, i+1);
20         try{
21             return Integer.valueOf(new String(arr));
22         }catch(Exception e){
23             return -1;
24         }
25     }
26
27     private void swap(char [] arr, int i, int j){
28         char temp = arr[i];
29         arr[i] = arr[j];
30         arr[j] = temp;
31     }
32
33     private void reverse(char [] arr, int start){
34         int i = start;
35         int j = arr.length-1;
36         while(i < j){
37             swap(arr, i++, j--);
38         }
39     }
40 }```