• ㊗️
• 大家
• offer
• 多多！

## Problem

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:

Input: n = 12
Output: 21


Example 2:

Input: n = 21
Output: -1


Constraints:

• $1 <= n <= 2^31 - 1$

## Code

31. Next Permutation

class Solution {
public int nextGreaterElement(int n) {
char[] arr = String.valueOf(n).toCharArray();

int i = arr.length - 2;
// 1. 找到第一个从左到右升序
while (i >= 0 && arr[i] >= arr[i + 1]) {
i--;
}

if (i < 0) return -1;

// 2. 从后往前 找到第一个比i大的数
int j = arr.length - 1;
while (j >= 0 && arr[j] <= arr[i]) {
j--;
}

swap(arr, i, j);
reverse(arr, i + 1);

// 2147483486
try {
return Integer.parseInt(new String(arr));
} catch (Exception e) {
return -1;
}
}

private void reverse(char[] arr, int start) {
int i = start;
int j = arr.length - 1;

while (i < j) {
swap(arr, i, j);
i++;
j--;
}
}

private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}