0801. Minimum Swaps To Make Sequences Increasing¶
题目信息¶
- 题号:
0801
- 难度:
Hard
- 主题:
数组、严格递增、最少交换
- 原题:
- 重点:
一次操作只能交换两个数组同一下标的元素;交换若干位置后两个数组都必须严格递增,并返回最少交换次数
题目重述¶
给定两个长度相同的整数数组 nums1 和 nums2。一次操作可以选择一个下标 i,交换 nums1[i] 与 nums2[i];不同下标可以分别决定是否交换。
请返回最少需要执行多少次交换,才能使 nums1 和 nums2 都严格递增,即各自满足每个后继元素都大于前一个元素。题目保证至少存在一种可行的交换方案。
两个数组长度均在 [2, 10^5] 范围内,元素值在 [0, 2 * 10^5] 范围内。
自建示例¶
只交换一个中间位置:
输入:nums1 = [1,6,5,10], nums2 = [2,3,8,11]
输出:1
解释:交换下标 1 后,两个数组变为 [1,3,5,10] 和 [2,6,8,11],都严格递增;原来的 nums1 在 6 与 5 之间不递增,因此至少需要一次交换。
无需交换:
输入:nums1 = [1,3,7], nums2 = [2,5,9]
输出:0
解释:两个数组原本都严格递增,不需要执行操作。