LeetCode每日一题：田忌赛马（最大胜场数）

870. 优势洗牌

给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        idx1, idx2 = list(range(n)), list(range(n))
        # 对每个元素的位次进行输出
        idx1.sort(key=lambda x: nums1[x])
        idx2.sort(key=lambda x: nums2[x])
        # print(idx1)

        ans = [0]*n 
        left, right = 0, n - 1
        # 田忌赛马
        for i in range(n):
            # 最低等马可以胜利，则直接得分
            if nums1[idx1[i]] > nums2[idx2[left]]:
                ans[idx2[left]] = nums1[idx1[i]]
                left += 1
            # 最低等马无法胜利，则去和对方最强马战斗
            else:
                ans[idx2[right]] = nums1[idx1[i]]
                right -= 1
        return ans