[LeetCode] 556. Next Greater Element III

轉自LeetCode

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

Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

<Solution>

Next Greater Element 的衍生題，但和前面兩題比較沒有關係

反而是和 31. Next Permutation 比較相近

這題簡單來說，其實就是找出下一個排列組合

例如 123，按照順序大小的下一個排列組合就是 132

想法如下

• 從數字尾端開始往前找，找到第一個降冪數字的位置；如果沒找到，就直接回傳 -1。例如1237985，紀錄 7 的位置

• 在排序的數字中，找到第一個比 7 大的數字，然後 swap。1238975

• 然後將 8 之後的數字，前後兩兩做swap。1238579。或是對 8 之後的數字做 sorting 也可以

• 檢查是不是大於 INT_MAX，是的話回傳 -1，不是的話就是答案

code如下

C++

Java

kotlin

C++有內建 next_permutation 的函式，也可以拿來使用