801.シーケンスを増やすための最小スワップ
801 Minimum Swaps Make Sequences Increasing
同じ非ゼロの長さの2つの整数列AとBがあります。
要素A [i]とB [i]を交換することができます。両方の要素がそれぞれのシーケンスで同じインデックス位置にあることに注意してください。
いくつかのスワップの終わりに、AとBは両方とも厳密に増加しています。 （A [0]の場合に限り、シーケンスは厳密に増加します。 AとBが与えられた場合、両方のシーケンスを厳密に増加させるために、スワップの最小数を返します。与えられた入力が常にそれを可能にすることが保証されています。 注意： A、Bは同じ長さの配列であり、その長さは[1、1000]の範囲になります。
Example: Input: A = [1,3,5,4], B = [1,2,3,7] Output: 1 Explanation: Swap A[3] and B[3]. Then the sequences are: A = [1, 3, 5, 7] and B = [1, 2, 3, 4] which are both strictly increasing.
A [i]、B [i]は、[0、2000]の範囲の整数値です。class Solution { public int minSwap(int[] A, int[] B) { // n: natural, s: swapped int n1 = 0, s1 = 1 for (int i = 1 i <A.length ++i) { int n2 = Integer.MAX_VALUE, s2 = Integer.MAX_VALUE if (A[i-1] <A[i] && B[i-1] <B[i]) { n2 = Math.min(n2, n1) s2 = Math.min(s2, s1 + 1) } if (A[i-1] <B[i] && B[i-1] <A[i]) { n2 = Math.min(n2, s1) s2 = Math.min(s2, n1 + 1) } n1 = n2 s1 = s2 } return Math.min(n1, s1) } }