> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/00_array/31.-next-permutation.md).

# 31. Next Permutation

<https://leetcode.com/problems/next-permutation/>

## solution

* Find the breakpoint from the end which breaks the non-increasing sequence. \[1, 3, 5, 4, 2] -> 3
* Traverse from end in right part and find the first element greater than breakpoint. \[1, 4, 5, 3, 2] -> 34互换
* Reverse the right part. \[1, 4, 2, 3, 5]

```python
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 如果第一部分用 for i in range(len(nums) -1, 0, -1)写法，会导致单元素的list为空. 且费时
        i = len(nums) - 1
        while i > 0:
            if nums[i-1] < nums[i]:
                break
            i -= 1

        pivot = i - 1
        if pivot == -1:
            nums.reverse()
            return

        for j in range(len(nums) - 1, pivot, -1):
            if nums[j] > nums[pivot]:
                nums[j], nums[pivot] = nums[pivot], nums[j]
                break

        # python list 可以这样局部更新
        nums[pivot+1:] = reversed(nums[pivot+1:])
```

时间复杂度：O(n)\
空间复杂度：O(1)

## follow up - 多步翻转法

[189. Rotate Array](https://leetcode.com/problems/rotate-array/description/)

```python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k]
```

* in-place

```python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        lens = len(nums)
        if k == lens:
            return
        k = k % lens
        self.reverse(nums, 0, lens-1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, lens-1)

    def reverse(self, nums, l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
```

[179. Largest Number](/mle-interview/01_leetcode/00_array/179.-largest-number.md)

剑指Offer 45: 把数组排成最小的数

```python
import functools

class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers:
            return ""
        num = list(map(str, numbers))
        cmp = lambda a, b: 1 if a + b > b + a else -1
        num = sorted(num, key=functools.cmp_to_key(cmp))
        return ''.join(num)
```

[186 Reverse Words in a String II](/mle-interview/01_leetcode/04_string/186.-reverse-words-in-a-string-ii.md)

[24. Swap Nodes in Pairs](/mle-interview/01_leetcode/02_linked_list/24.-swap-nodes-in-pairs.md)

[556. Next Greater Element III](https://leetcode.com/problems/next-greater-element-iii/description/)

```python
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        str_num = str(n)
        if len(str_num) <= 1:
            return -1

        i = len(str_num) - 1
        while i > 0:
            if str_num[i-1] >= str_num[i]:
                i -= 1
            else:
                break

        if i == 0:
            return -1

        pivot = i - 1
        j = len(str_num) - 1
        str_num_list = list(str_num)
        while j >= i - 1:
            if str_num[j] > str_num[pivot]:
                str_num_list[j], str_num_list[pivot] = str_num_list[pivot], str_num_list[j]
                break
            else:
                j -= 1

        str_num_list[pivot+1:] = reversed(str_num_list[pivot+1:])
        res = int(''.join(str_num_list))
        if res > 2**31 - 1:
            return -1
        return res
```