洛谷 p1088 火星人解题思路

洛谷 p1088 火星人是一道经典的排列组合问题，要求我们找到给定排列的下一个排列。具体解题思路如下：

1. **从后向前找到第一个下降的点**：
- 从数组的末尾开始向前遍历，找到第一个满足 `nums[i] < nums[i+1]` 的位置 `i`。如果找不到这样的位置，说明该排列已经是字典序最大的排列，直接返回字典序最小的排列（即反转整个数组）。

2. **从后向前找到第一个大于 `nums[i]` 的数**：
- 再次从数组的末尾开始向前遍历，找到第一个大于 `nums[i]` 的位置 `j`。交换 `nums[i]` 和 `nums[j]`。

3. **反转 `i+1` 到末尾的部分**：
- 将 `i+1` 到末尾的部分反转，使其成为字典序最小的排列。

通过以上步骤，我们可以找到给定排列的下一个排列。

以下是一个Python代码示例：

def nextPermutation(nums):
    n = len(nums)
    i = n - 2
    # 找到第一个下降的点
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        # 找到第一个大于 nums[i] 的数
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        # 交换 nums[i] 和 nums[j]
        nums[i], nums[j] = nums[j], nums[i]
    # 反转 i+1 到末尾的部分
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

# 示例
nums = [1, 2, 3]
nextPermutation(nums)
print(nums)  # 输出 [1, 3, 2]