leetcode 556. 下一个更大元素 III

题解

n 转为字节数组 b,首先从右到左找到 b[i-1] < b[i] 表明有更大的值大于 n(但不一定是最小的),然后在 b[i:] 里找到大于 b[i-1] 的最小值 b[j],接着交换 b[i-1], b[j],反转 b[i:] 按升序排列

示例代码(go)

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
func nextGreaterElement(n int) int {
b := []byte(strconv.Itoa(n))
for i := len(b)-1; i > 0; i-- {
if b[i-1] < b[i] {
for j := len(b)-1; j >= i; j-- {
if b[j] > b[i-1] {
b[j], b[i-1] = b[i-1], b[j]
reverse(b, i)
break
}
}
break
}
}
res, _ := strconv.Atoi(string(b))
if res == n || res > math.MaxInt32 {
return -1
}
return res
}

func reverse(b []byte, i int) {
l, r := i, len(b)-1
for l < r {
b[l], b[r] = b[r], b[l]
l++
r--
}
}