题解 | #换位#_牛客博客

题目的主要信息：

给出两个等长的数列，求使第一个数列严格降序，第二个数列严格升序的最少交换次数
交换是指第一个数组中相对应的位置交换到第二个数组相对应位置
若无法交换成严格有序，返回“-1”

方法一：动态规划

具体做法：
我们用两个动态规划数组来描述，其中dp1[i]表示第i个元素不需要调整即可满足要求，最少调整dp1[i]次，dp2[i]表示第i个元素需要调整才可以满足要求，最少调整dp2[i]次。初始时，必定有 $dp1[0]=0$ 和 $dp2[0]=1$ .我们遍历数组，两个数组的相邻两元素进行下面四种检查：（i表示当前元素也即后一个元素）

如果数组1相邻两个元素递减，数组2相邻两个元素递增，那么我们不需要调整，有 $dp1[i] = dp1[i - 1]$ ;
如果数组1相邻两个元素递增，而数组2相邻两个元素递减，我们需要在之前调整的基础上在加一次调整，即两个位置都要交换，有 $dp2[i]=dp2[i-1]+1$ ，前提是这里的 $dp2[i-1]$ 是有的，能够调整的，否则无法加；
如果数组1前一个元素小于数组2后一个元素，而数组1的后一个元素小于数组2的前一个元素，即数组1相邻两个元素交叉小于数组2对应的两个元素，那我们将第 $i-1$ 个位置的两个元素交换，即有 $dp1[i] = min(dp1[i], dp2[i - 1])$
如果数组1前一个元素大于数组2后一个元素，而数组1的后一个元素大于数组2的前一个元素，即数组1相邻两个元素交叉大于数组2对应的两个元素，即后一个位置需要交换，即有 $dp2[i] = min(dp2[i], dp1[i - 1] + 1)$

上面的比较全是严格大于小于的，如果有其他情况导致两个dp数组都没有降下来，就说明无法调整到题目要求的情况，返回-1，否则返回 $min(dp1[n - 1], dp2[n - 1])$ .
图片说明

class Solution {
public:
    int arrange(vector<int>& firstRow, vector<int>& secondRow) {
        int n = firstRow.size();
        vector<int> dp1(n, INT_MAX); //dp1[i]表示第i个元素不需要调整即可满足要求，最少调整dp1[i]次
        vector<int> dp2(n, INT_MAX); //dp2[i]表示第i个元素需要调整才可以满足要求，最少调整dp2[i]次
        dp1[0] = 0; //初始化
        dp2[0] = 1;
        for(int i = 1; i < n; i++){ //遍历数组开始检验
            if(firstRow[i] < firstRow[i - 1] && secondRow[i] > secondRow[i - 1])
                dp1[i] = dp1[i - 1]; //满足要求，不需要调整
            if(firstRow[i] > firstRow[i - 1] && secondRow[i] < secondRow[i - 1]) //两边序列都是相反
                if(dp2[i - 1] != INT_MAX)
                    dp2[i] = dp2[i - 1] + 1; //在之前的基础上+1如果之前有的话，否则无法交换
            if(firstRow[i] < secondRow[i - 1] && secondRow[i] > firstRow[i - 1])
                dp1[i] = min(dp1[i], dp2[i - 1]); //当前元素不调整  之前i-1调整
            if(firstRow[i] > secondRow[i - 1] && secondRow[i] < firstRow[i - 1])
                if(dp1[i - 1] != INT_MAX)
                    dp2[i] = min(dp2[i], dp1[i - 1] + 1); //必须在i-1元素不调整的情况下  交换当前元素
        }
        int res = min(dp1[n - 1], dp2[n - 1]);//取较小值
        return res == INT_MAX ? -1 : res; //如果全是无法交换则无法严格有序
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(n)$ ，两个辅助数组的长度都是 $n$

方法二：动态规划空间优化

具体做法：
方法一的动态规划数组，我们只使用到了第 $i$ 项和第 $i+1$ 项，因此我们可以只准备两项，使用 $x = 1 - x$ 来交替使用两列数组，数组第二维则代表刚刚的dp1和dp2.

class Solution {
public:
    int arrange(vector<int>& firstRow, vector<int>& secondRow) {
        int n = firstRow.size();
        vector<vector<int> > dp(2, vector<int>(2, INT_MAX));
        int x = 0;
        dp[x][0] = 0;
        dp[x][1] = 1;
        for(int i = 1; i < n; i++){ //遍历数组开始检验
            x = 1 - x;
            dp[x][0] = INT_MAX;
            dp[x][1] = INT_MAX;
            if(firstRow[i] < firstRow[i - 1] && secondRow[i] > secondRow[i - 1])
                dp[x][0] = dp[1 - x][0]; //满足要求，不需要调整
            if(firstRow[i] > firstRow[i - 1] && secondRow[i] < secondRow[i - 1]) //两边序列都是相反
                if(dp[1 - x][1] != INT_MAX)
                    dp[x][1] = dp[1 - x][1] + 1; //在之前的基础上+1如果之前有的话，否则无法交换
            if(firstRow[i] < secondRow[i - 1] && secondRow[i] > firstRow[i - 1])
                dp[x][0] = min(dp[x][0], dp[1 - x][1]); //当前元素不调整  之前i-1调整
            if(firstRow[i] > secondRow[i - 1] && secondRow[i] < firstRow[i - 1])
                if(dp[1 - x][0] != INT_MAX)
                    dp[x][1] = min(dp[x][1], dp[1 - x][0] + 1); //必须在i-1元素不调整的情况下  交换当前元素
        }
        int res = min(dp[x][0], dp[x][1]);//取较小值
        return res == INT_MAX ? -1 : res; //如果全是无法交换则无法严格有序
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(1)$ ，常数级空间，数组dp相当于4个变量