刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/create-maximum-number/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 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]

思路

这道题跟402、316题类似，都可以考虑*单调栈*的思路。但是这道题加了一个难度，需要从两个数组中拼出一个最大数组，需要有一个分治的思维，把问题转化成：从两个数组中分别取出i、j长的两个数组，拼装合并起来之后，取最大的一个，条件是，i <= len(nums1) 且 j <= len(nums2)、i + j = k 。而至于拼装等功能函数，其实还是比较简单的

代码

func maxSubsequence(a []int, k int) (s []int) {
    removeNum := len(a)-k
    for _, v := range a {
        for len(s) > 0 && removeNum > 0 && v > s[len(s)-1] {
            s = s[:len(s)-1]
            removeNum--
        }
        s = append(s, v)
    }
    if len(s) > k {
        s = s[:k]
    }
    return
}

func biggerSlice(a, b []int) bool {
    for i := 0; i < len(a) && i < len(b); i++ {
        if a[i] != b[i] {
            return a[i] < b[i]
        }
    }
    return len(a) < len(b)
}

func merge(a, b []int) []int {
    merged := make([]int, len(a)+len(b))
    for i := range merged {
        if biggerSlice(a, b) {
            merged[i], b = b[0], b[1:]
        } else {
            merged[i], a = a[0], a[1:]
        }
    }
    return merged
}

func maxNumber(nums1, nums2 []int, k int) (res []int) {
    start := 0
    if k > len(nums2) {
        start = k - len(nums2)
    }
    for i := start; i <= k && i <= len(nums1); i++ {
        s1 := maxSubsequence(nums1, i)
        s2 := maxSubsequence(nums2, k-i)
        merged := merge(s1, s2)
        if biggerSlice(res, merged) {
            res = merged
        }
    }
    return
}