主題
題目: 801. Minimum Swaps To Make Sequences Increasing
難度: Hard
目前下列解法的時間複雜度: O(n)
題目說明
給定二長度 n 的 0-indexed 的整數陣列，問「花最少次數將兩陣列同索引之數值交換，使這兩陣列都變成嚴格遞增陣列」的次數是多少。
解法：分析後從頭滑到尾
1. 會違反「嚴格遞增」只要觀察到相鄰的元素違反即可，意即索引 i 頂多看 i+1 （或 i-1 ，如果你比較喜歡往後看，反正一前一後）。
2. 在完成好的兩條「嚴格遞增」陣列中，原本的 i 與 i+1 只可能是：
a. 兩條陣列中的 i 的最大值 < 兩條陣列中的 i+1 的最小值。則此時前面的部分與後面的部分無關了（前面怎麼換不影響後面怎麼換）。
b. 不是a的情況，可能換 i ，也可能換 i+1 ，或者不動，但不會都換。
先想像沒有 a 情形發生，只考慮 b ，如果「交換的次數」 > 「 陣列長度-交換次數」，那麼兩條陣列直接對調，交換次數立刻變成了「陣列長度-原交換次數」 < 原交換次數。所以沒有a情形的交換次數是 min( 陣列長度-交換次數 , 交換次數 )。
再來考慮有 a 的情形，「 i 及其之前」與「 i+1 及其之後」並無關聯，前面的交換不影響後面。
=> 用 a 情形切成多個片段，每個片段中遇到違反「嚴格遞增」的情形就直接交換，最後該段的答案是 min( 陣列長度-交換次數 , 交換次數 ) 。
3. 每段的答案加起來回傳。
source code
難度: Hard
目前下列解法的時間複雜度: O(n)
題目說明
給定二長度 n 的 0-indexed 的整數陣列，問「花最少次數將兩陣列同索引之數值交換，使這兩陣列都變成嚴格遞增陣列」的次數是多少。
解法：分析後從頭滑到尾
1. 會違反「嚴格遞增」只要觀察到相鄰的元素違反即可，意即索引 i 頂多看 i+1 （或 i-1 ，如果你比較喜歡往後看，反正一前一後）。
2. 在完成好的兩條「嚴格遞增」陣列中，原本的 i 與 i+1 只可能是：
a. 兩條陣列中的 i 的最大值 < 兩條陣列中的 i+1 的最小值。則此時前面的部分與後面的部分無關了（前面怎麼換不影響後面怎麼換）。
b. 不是a的情況，可能換 i ，也可能換 i+1 ，或者不動，但不會都換。
先想像沒有 a 情形發生，只考慮 b ，如果「交換的次數」 > 「 陣列長度-交換次數」，那麼兩條陣列直接對調，交換次數立刻變成了「陣列長度-原交換次數」 < 原交換次數。所以沒有a情形的交換次數是 min( 陣列長度-交換次數 , 交換次數 )。
再來考慮有 a 的情形，「 i 及其之前」與「 i+1 及其之後」並無關聯，前面的交換不影響後面。
=> 用 a 情形切成多個片段，每個片段中遇到違反「嚴格遞增」的情形就直接交換，最後該段的答案是 min( 陣列長度-交換次數 , 交換次數 ) 。
3. 每段的答案加起來回傳。
source code
