?LeetCode刷題實(shí)戰(zhàn)321：拼接最大數(shù)

示例 1:

輸入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
輸出:
[9, 8, 6, 5, 3]

示例 2:

輸入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
輸出:
[6, 7, 6, 0, 4]

示例 3:

輸入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
輸出:
[9, 8, 9]

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def pick_max(num, k):#從列表中找到最大的k個(gè)數(shù)組合（不改變位置）
            n = len(num)
            drop = n - k#計(jì)算需要丟棄的數(shù)字個(gè)數(shù)
            stack = []
            for i in range(n):#對(duì)之后的每個(gè)數(shù)進(jìn)行比較
                while drop and stack and num[i] > stack[-1]:#待加入的值比棧頂?shù)闹荡螅瑒t棧頂彈出，丟棄值減一
                    stack.pop()
                    drop -= 1
                stack.append(num[i])#入棧
            return stack[:k]#輸出需要的長(zhǎng)度，因?yàn)榱斜砜赡苁沁f減的

        def merge(num1, num2, k):
            out = []
            m, n = len(num1), len(num2)
            for i in range(k+1):#每個(gè)組中循環(huán)取 0-k共k+1個(gè)數(shù)
                if i <= m and k-i <= n:#注意這里必須對(duì)循環(huán)的索引進(jìn)行限制，非則會(huì)越界
                    res = []
                    res1 = pick_max(num1, i)#得到列表1中的最大子列表
                    res2 = pick_max(num2, k-i)#得到列表2中的最大子列表
                    print(res1, res2)
                    while res1 or res2:#開(kāi)始合并，當(dāng)兩者都為空的時(shí)候才停止
                        ans = res1 if res1 > res2 else res2#兩個(gè)子列表的中較大的一個(gè)賦給ans,這里是引用
                        res.append(ans[0])#本次輸出res,連接較大列表的首個(gè)數(shù)字，之后再?gòu)棾?/span>
                        ans.pop(0)#這里的ans彈出左邊的值，也等于res1或者res2中較大的一個(gè)彈出左值，因?yàn)榱斜頌橐?/span>
                    out = max(out, res) #對(duì)所有的組合中去一個(gè)最大的作為輸出
            return out 
        return merge(nums1, nums2, k)