556. Next Greater Element III

发表于 | 分类于 | |

556. Next Greater Element III

题目描述

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

1
2
3
Example 1:
Input: 12
Output: 21
1
2
3
Example 2:
Input: 21
Output: -1

题目大意

给一数值n，满足以下条件的值 ans ：

  • 不大于0x7FFFFFFF
  • 大于n
  • ans包含n中所有的数。

符合条件则返回ans，否则返回-1。

解题思路

转n为数组。
反向遍历数组，找到最后一个递增下标index。
如果存在递增下标，则反向遍历数组，将nums[index - 1]，与最后一个大于nums[index - 1]进行替换。
由于index之后的元素呈递减序列，所以采用双指针的方式交换元素。

代码

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
class Solution {
     func nextGreaterElement(_ n: Int) -> Int {
        var index = 0
        var s = Array("\(n)")
        
        for i in (1..<s.count).reversed() {
            if s[i - 1] < s[i] {
                index = i
                break
            }
        }
        
        if index > 0 {
            for i in (0..<s.count).reversed() {
                if s[i] > s[index - 1] {
                    s.swapAt(index - 1, i)
                    break
                }
            }
        }
        
        for i in 0..<(s.count - index) / 2 {
            s.swapAt(index + i, s.count - i - 1)
        }
        let ans = Int(String(s))!
        return ans > n && ans <= 0x7FFFFFFF ? ans : -1
    }
}
0%