[路飞]_321. 拼接最大数-一一网

题目

给定长度分别为 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]
复制代码

题解

单调栈

示例中：
$nums1 = [3, 4, 6, 5]$
$nums2 = [9, 1, 2, 5, 8, 3]$

示例中所有又可能的最大睡数可以是：

最大数全部在 $nums1$ 中
最大数全部在 $nums2$ 中
最大数部分在 $nums1$ 中，部分在 $nums2$ 中；

所以此处需要一个枚举；

在 $nums1$ 中找 $i$ 个最大值并在 $nums2$ 找 $k-i$ 个最大值组成的所有可能的最大值即位题目答案

for(let i = 0 ; i < k ; i++){
    const list1 = helper(nums1,i)
    const list2 = helper(nums2,k-i)
}
复制代码

现在题目可以转换为数组中找指定数量元素组成的最大值，很显然这可以用单调栈解决

寻找数组中不改变顺序指定数量组成的最大值的方法如下：

  function helper(array, limit) {
    if (limit === 0) return []
    if (limit >= array.length) return array
    const stack = []
    let index = 0
    const len = array.length
    while (index < len) {
      while (
        stack.length &&
        stack[stack.length - 1] < array[index] &&
        stack.length + len - index - 1 >= limit
      ) {
        stack.pop()
      }
      stack.push(array[index++])
    }
    return stack.slice(0, limit)
  }
}
复制代码

找到数组中最大值还需要合并数组，因为现在得到了两个数组list1和list2，要将两个顺序数组组成一个较大数组，这个也是一个难点

合并数组比如 $[6,7]$ [6,4 $]$ ;组成的最大值应该是 $[6,7,6,4]$

合并两个数组的时候：

数组长度不同，长度较长的数组较大
如果数组成都相同，数组中单独节点比较
- 当前两数组节点较大的数组大
- 当前两数组节点元素相同，比较两数组下一位元素

合并两个数组得到最大值这个难度也快赶上中等难度题了；解决这题的时候就在这里花的时间最多。这里难哭了

 // 找到数组1和2谁打
  function check(a1, index1, a2, index2) {
    while (index1 < a1.length && index2 < a2.length) {
      const diff = a1[index1] - a2[index2]
      if (diff !== 0) return diff
      index1++
      index2++
    }
    return a1.length - index1 - (a2.length - index2)
  }

  // 合并两个有序数组
  function compose(ary1, ary2) {
    const list = []
    const len1 = ary1.length
    const len2 = ary2.length
    let index1 = 0
    let index2 = 0
    for (let i = 0; i < len1 + len2; i++) {
      if (check(ary1, index1, ary2, index2) > 0) {
        list[i] = ary1[index1++]
      } else {
        list[i] = ary2[index2++]
      }
    }
    return list
  }
复制代码

然后就是拿到的合并后的数组，找到数组中最大的那个即可；因为数组可能很长，不能将数组转换为数组进行比较，所以需要将数组逐一对比；

根据上述思路编辑代码如下：

var maxNumber = function (nums1, nums2, k) {
  let max = null
  for (let i = 0; i <= k; i++) {
    if (k - i > nums2.length) continue
    if (i > nums1.length) continue
    const list1 = helper(nums1, i)
    const list2 = helper(nums2, k - i)
    const current = compose(list1, list2)
    if (max) {
      max = computMaxArray(max, current)
    } else {
      max = current
    }
  }
  return max

  function computMaxArray(ary1, ary2) {
    if (ary1.length === 0) return ary2
    if (ary2.length === 0) return ary1
    if (ary1.length > ary2.length) return ary1
    if (ary1.length < ary2.length) return ary2
    let index = 0
    while (index < ary1.length) {
      if (ary1[index] > ary2[index]) {
        return ary1
      } else if (ary1[index] < ary2[index]) {
        return ary2
      }
      index++
    }
    return ary2
  }
  // 找到数组1和2谁打
  function check(a1, index1, a2, index2) {
    while (index1 < a1.length && index2 < a2.length) {
      const diff = a1[index1] - a2[index2]
      if (diff !== 0) return diff
      index1++
      index2++
    }
    return a1.length - index1 - (a2.length - index2)
  }

  // 合并两个有序数组
  function compose(ary1, ary2) {
    const list = []
    const len1 = ary1.length
    const len2 = ary2.length
    let index1 = 0
    let index2 = 0
    for (let i = 0; i < len1 + len2; i++) {
      if (check(ary1, index1, ary2, index2) > 0) {
        list[i] = ary1[index1++]
      } else {
        list[i] = ary2[index2++]
      }
    }
    return list
  }
  function helper(array, limit) {
    if (limit === 0) return []
    if (limit >= array.length) return array
    const stack = []
    let index = 0
    const len = array.length
    while (index < len) {
      while (
        stack.length &&
        stack[stack.length - 1] < array[index] &&
        stack.length + len - index - 1 >= limit
      ) {
        stack.pop()
      }
      stack.push(array[index++])
    }
    return stack.slice(0, limit)
  }
}
复制代码