1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public int nextGreaterElement(int n) {
String numString = String.valueOf(n);
char[] numCharArray = numString.toCharArray();
int pos = -1;
for (int i = numCharArray.length - 1; i > 0; i--) {
if (numCharArray[i] > numCharArray[i - 1]) {
pos = i - 1;
break;
}
}
if (pos == -1) {
return -1;
}
int newPos = -1;
for (int i = numCharArray.length - 1; i >= 0; i--) {
if (numCharArray[i] > numCharArray[pos]) {
newPos = i;
break;
}
}
swap(numCharArray, pos, newPos);
reverse(numCharArray, pos + 1, numCharArray.length - 1);
int ans = 0;
for (int i = 0; i < numCharArray.length; i++) {
if (ans > Integer.MAX_VALUE / 10
|| (ans == Integer.MAX_VALUE / 10 && numCharArray[i] - '0' > Integer.MAX_VALUE % 10)) {
return -1;
}
ans = ans * 10 + numCharArray[i] - '0';
}
return ans;
}
private void swap(char[] numCharArray, int i, int j) {
char temp = numCharArray[i];
numCharArray[i] = numCharArray[j];
numCharArray[j] = temp;
}
private void reverse(char[] numCharArray, int left, int right) {
while (left < right) {
swap(numCharArray, left, right);
left += 1;
right -= 1;
}
}
}
|
Next permutaion.
还有一点要注意的是如何判断是否会出界也就是27和28行需要牢牢记得.
时间复杂度: O(n)
空间复杂度: O(n) 我们使用了numCharArray.
