# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://longxingtan.gitbook.io/mle-interview/01_leetcode/00_array/31.-next-permutation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.