## 题目描述：

LeetCode 801. Minimum Swaps To Make Sequences Increasing

We have two integer sequences `A` and `B` of the same non-zero length.

We are allowed to swap elements `A[i]` and `B[i]`.  Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, `A` and `B` are both strictly increasing.  (A sequence is strictly increasing if and only if `A < A < A < ... < A[A.length - 1]`.)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing.  It is guaranteed that the given input always makes it possible.

```Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation:
Swap A and B.  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.
```

Note:

• `A, B` are arrays with the same length, and that length will be in the range `[1, 1000]`.
• `A[i], B[i]` are integer values in the range `[0, 2000]`.

## 解题思路：

`swap和keep分别记录A[i]与B[i]交换或者不交换时的最小代价`

`A[i]与B[i]必须交换`
`A[i]与B[i]可以交换也可以保持原状`
`A[i]与B[i]必须保持原状`

## Python代码：

``````class Solution(object):
def minSwap(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
swap, keep = 1, 0
for i in range(1, len(A)):
if A[i] <= A[i - 1] or B[i] <= B[i - 1]:
# swap
nswap = keep + 1
nkeep = swap
elif A[i] > B[i - 1] and B[i] > A[i - 1]:
# swap or keep
nkeep = min(keep, swap)
nswap = nkeep + 1
else:
# keep
nkeep = keep
nswap = swap + 1
swap, keep = nswap, nkeep
return min(swap, keep)
``````

Pingbacks已关闭。