---
# System prepended metadata

title: 0556. Next Greater Element III
tags: [Leetcode, FaceBook, Medium]

---

# 0556. Next Greater Element III
###### tags: `Leetcode` `FaceBook` `Medium`
Link: https://leetcode.com/problems/next-greater-element-iii/
## 思路
和[0031. Next Permutation](https://hackmd.io/TsbCCO9UTJK23dz4ewwVbQ)是一样的

从后往前找，如果这一位大于或等于它的后一位，则跳过。如果这一位小于它的后一位，那么就把这一位后面所有位里面数字最小的但是又比这一位大的那个和这一位调换，再把它后面reverse
用reverse的原因是已经通过line 6~10的回圈检查过后面是从大到小排列了，所以只要reverse改成从小到大排列就可以了

唯一的差别就是如果发现结果超过int范围就返回-1

注意：
- 这里把各个位拆开，用的是先变成string，然后toCharArray
- 判断结果会不会超过int范围 用的是try and catch 要记住语法
```java=
try{
    return Integer.parseInt(new String(num));
}
catch(Exception e){
    return -1;
}
```
- 第18行**一定要用大于等于**
原因如下：如果原数字是2333，那么decreaseIdx就是0，swapIdx需要是3，而不是1，因为如果是1的话，就会变成3233，然后reverse就会变成3332
## Code
```java=
class Solution {
    public int nextGreaterElement(int n) {
        char[] num = String.valueOf(n).toCharArray();
        int decreaseIdx = num.length-2;
        
        while(decreaseIdx>=0){
            if(num[decreaseIdx]<num[decreaseIdx+1]){
                break;
            }
            decreaseIdx--;
        }
        if(decreaseIdx == -1){
            return -1;
        }
        
        int swapIdx = decreaseIdx+1;
        for(int i = swapIdx;i < num.length;i++){
            if(num[decreaseIdx]<num[i] && num[i]<=num[swapIdx]){
                swapIdx = i;
            }
        }
        
        swap(num, swapIdx, decreaseIdx);
        reverse(num, decreaseIdx+1);
        
        try{
            return Integer.parseInt(new String(num));
        }
        catch(Exception e){
            return -1;
        }
    }
    
    public void swap(char[] num, int a, int b){
        char temp = num[a];
        num[a] = num[b];
        num[b] = temp;
    }
    
    public void reverse(char[] num, int start){
        int end = num.length-1;
        while(start<end){
            swap(num, start, end);
            start++;
            end--;
        }
    }
}
```