一、题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，以及两个整数 m 和 n。
nums1的长度为m + n- 前
m个元素为有效元素 - 后
n个元素为 0（占位） nums2长度为n
要求：
将 nums2 合并到 nums1 中，使结果仍然保持非递减顺序。
注意： 必须 原地修改 nums1，不能返回新数组。
二、示例
示例 1
输入： nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出： [1,2,2,3,5,6]
示例 2
输入： nums1 = [1], m = 1 nums2 = [], n = 0
输出： [1]
示例 3
输入： nums1 = [0], m = 0 nums2 = [1], n = 1
输出： [1]
三、错误思路分析（为什么不能从前往后合并）
很多人第一反应：
从前往后比较，小的放前面。
问题是：
- nums1 前面是有效数据
- 后面是 0 占位
- 如果从前往后插入，会覆盖还未比较的数据
举例：
nums1 = [1,2,3,0,0,0] nums2 = [2,5,6]
如果从前面开始插入，后面的 3 可能会被覆盖。
四、正确思路 —— 从后往前双指针（核心）
关键思想：
既然后面有空位，那就从后往前填！
定义三个指针
i = m - 1 // nums1 有效元素最后一个 j = n - 1 // nums2 最后一个 k = m + n - 1 // nums1 总数组最后一个位置
处理逻辑
- 比较 nums1[i] 和 nums2[j]
- 较大的放到 nums1[k]
- 指针向前移动
- 重复直到 nums2 用完
五、图解过程
示例：
nums1 = [1,2,3,0,0,0] nums2 = [2,5,6]
初始：
i -> 3 j -> 6 k -> 最后位置
步骤：
| 比较 | 放入 | 数组变成 |
|---|---|---|
| 3 vs 6 | 6 | [1,2,3,0,0,6] |
| 3 vs 5 | 5 | [1,2,3,0,5,6] |
| 3 vs 2 | 3 | [1,2,3,3,5,6] |
| 2 vs 2 | 2 | [1,2,2,3,5,6] |
