Question

321. 拼接最大数

English Version

题目描述

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

提示：

• m == nums1.length
• n == nums2.length
• 1 <= m, n <= 500
• 0 <= nums1[i], nums2[i] <= 9
• 1 <= k <= m + n

解法

方法一：枚举 + 单调栈

我们可以枚举从数组 $nums1$ 中取出 $x$ 个数，那么从数组 $nums2$ 中就需要取出 $k-x$ 个数。其中 $x \in [max(0, k-n), min(k, m)]$。

对于每一个 $x$，我们可以使用单调栈求出数组 $nums1$ 中长度为 $x$ 的最大子序列，以及数组 $nums2$ 中长度为 $k-x$ 的最大子序列。然后将这两个子序列合并得到长度为 $k$ 的最大子序列。

最后，我们比较所有的长度为 $k$ 的最大子序列，找出最大的序列即可。

时间复杂度 $O(k \times (m + n + k^2))$，空间复杂度 $O(k)$。其中 $m$ 和 $n$ 分别是数组 $nums1$ 和 $nums2$ 的长度。

class Solution:
  def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
    def f(nums: List[int], k: int) -> List[int]:
      n = len(nums)
      stk = [0] * k
      top = -1
      remain = n - k
      for x in nums:
        while top >= 0 and stk[top] < x and remain > 0:
          top -= 1
          remain -= 1
        if top + 1 < k:
          top += 1
          stk[top] = x
        else:
          remain -= 1
      return stk

    def compare(nums1: List[int], nums2: List[int], i: int, j: int) -> bool:
      if i >= len(nums1):
        return False
      if j >= len(nums2):
        return True
      if nums1[i] > nums2[j]:
        return True
      if nums1[i] < nums2[j]:
        return False
      return compare(nums1, nums2, i + 1, j + 1)

    def merge(nums1: List[int], nums2: List[int]) -> List[int]:
      m, n = len(nums1), len(nums2)
      i = j = 0
      ans = [0] * (m + n)
      for k in range(m + n):
        if compare(nums1, nums2, i, j):
          ans[k] = nums1[i]
          i += 1
        else:
          ans[k] = nums2[j]
          j += 1
      return ans

    m, n = len(nums1), len(nums2)
    l, r = max(0, k - n), min(k, m)
    ans = [0] * k
    for x in range(l, r + 1):
      arr1 = f(nums1, x)
      arr2 = f(nums2, k - x)
      arr = merge(arr1, arr2)
      if ans < arr:
        ans = arr
    return ans

class Solution {
  public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int m = nums1.length, n = nums2.length;
    int l = Math.max(0, k - n), r = Math.min(k, m);
    int[] ans = new int[k];
    for (int x = l; x <= r; ++x) {
      int[] arr1 = f(nums1, x);
      int[] arr2 = f(nums2, k - x);
      int[] arr = merge(arr1, arr2);
      if (compare(arr, ans, 0, 0)) {
        ans = arr;
      }
    }
    return ans;
  }

  private int[] f(int[] nums, int k) {
    int n = nums.length;
    int[] stk = new int[k];
    int top = -1;
    int remain = n - k;
    for (int x : nums) {
      while (top >= 0 && stk[top] < x && remain > 0) {
        --top;
        --remain;
      }
      if (top + 1 < k) {
        stk[++top] = x;
      } else {
        --remain;
      }
    }
    return stk;
  }

  private int[] merge(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int i = 0, j = 0;
    int[] ans = new int[m + n];
    for (int k = 0; k < m + n; ++k) {
      if (compare(nums1, nums2, i, j)) {
        ans[k] = nums1[i++];
      } else {
        ans[k] = nums2[j++];
      }
    }
    return ans;
  }

  private boolean compare(int[] nums1, int[] nums2, int i, int j) {
    if (i >= nums1.length) {
      return false;
    }
    if (j >= nums2.length) {
      return true;
    }
    if (nums1[i] > nums2[j]) {
      return true;
    }
    if (nums1[i] < nums2[j]) {
      return false;
    }
    return compare(nums1, nums2, i + 1, j + 1);
  }
}

class Solution {
public:
  vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    auto f = [](vector<int>& nums, int k) {
      int n = nums.size();
      vector<int> stk(k);
      int top = -1;
      int remain = n - k;
      for (int x : nums) {
        while (top >= 0 && stk[top] < x && remain > 0) {
          --top;
          --remain;
        }
        if (top + 1 < k) {
          stk[++top] = x;
        } else {
          --remain;
        }
      }
      return stk;
    };
    function<bool(vector<int>&, vector<int>&, int, int)> compare = [&](vector<int>& nums1, vector<int>& nums2, int i, int j) -> bool {
      if (i >= nums1.size()) {
        return false;
      }
      if (j >= nums2.size()) {
        return true;
      }
      if (nums1[i] > nums2[j]) {
        return true;
      }
      if (nums1[i] < nums2[j]) {
        return false;
      }
      return compare(nums1, nums2, i + 1, j + 1);
    };

    auto merge = [&](vector<int>& nums1, vector<int>& nums2) {
      int m = nums1.size(), n = nums2.size();
      int i = 0, j = 0;
      vector<int> ans(m + n);
      for (int k = 0; k < m + n; ++k) {
        if (compare(nums1, nums2, i, j)) {
          ans[k] = nums1[i++];
        } else {
          ans[k] = nums2[j++];
        }
      }
      return ans;
    };

    int m = nums1.size(), n = nums2.size();
    int l = max(0, k - n), r = min(k, m);
    vector<int> ans(k);
    for (int x = l; x <= r; ++x) {
      vector<int> arr1 = f(nums1, x);
      vector<int> arr2 = f(nums2, k - x);
      vector<int> arr = merge(arr1, arr2);
      if (ans < arr) {
        ans = move(arr);
      }
    }
    return ans;
  }
};

func maxNumber(nums1 []int, nums2 []int, k int) []int {
  m, n := len(nums1), len(nums2)
  l, r := max(0, k-n), min(k, m)
  f := func(nums []int, k int) []int {
    n := len(nums)
    stk := make([]int, k)
    top := -1
    remain := n - k
    for _, x := range nums {
      for top >= 0 && stk[top] < x && remain > 0 {
        top--
        remain--
      }
      if top+1 < k {
        top++
        stk[top] = x
      } else {
        remain--
      }
    }
    return stk
  }

  var compare func(nums1, nums2 []int, i, j int) bool
  compare = func(nums1, nums2 []int, i, j int) bool {
    if i >= len(nums1) {
      return false
    }
    if j >= len(nums2) {
      return true
    }
    if nums1[i] > nums2[j] {
      return true
    }
    if nums1[i] < nums2[j] {
      return false
    }
    return compare(nums1, nums2, i+1, j+1)
  }

  merge := func(nums1, nums2 []int) []int {
    m, n := len(nums1), len(nums2)
    ans := make([]int, m+n)
    i, j := 0, 0
    for k := range ans {
      if compare(nums1, nums2, i, j) {
        ans[k] = nums1[i]
        i++
      } else {
        ans[k] = nums2[j]
        j++
      }
    }
    return ans
  }

  ans := make([]int, k)
  for x := l; x <= r; x++ {
    arr1 := f(nums1, x)
    arr2 := f(nums2, k-x)
    arr := merge(arr1, arr2)
    if compare(arr, ans, 0, 0) {
      ans = arr
    }
  }
  return ans
}

function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
  const m = nums1.length;
  const n = nums2.length;
  const l = Math.max(0, k - n);
  const r = Math.min(k, m);
  let ans: number[] = Array(k).fill(0);
  for (let x = l; x <= r; ++x) {
    const arr1 = f(nums1, x);
    const arr2 = f(nums2, k - x);
    const arr = merge(arr1, arr2);
    if (compare(arr, ans, 0, 0)) {
      ans = arr;
    }
  }
  return ans;
}

function f(nums: number[], k: number): number[] {
  const n = nums.length;
  const stk: number[] = Array(k).fill(0);
  let top = -1;
  let remain = n - k;
  for (const x of nums) {
    while (top >= 0 && stk[top] < x && remain > 0) {
      --top;
      --remain;
    }
    if (top + 1 < k) {
      stk[++top] = x;
    } else {
      --remain;
    }
  }
  return stk;
}

function compare(nums1: number[], nums2: number[], i: number, j: number): boolean {
  if (i >= nums1.length) {
    return false;
  }
  if (j >= nums2.length) {
    return true;
  }
  if (nums1[i] > nums2[j]) {
    return true;
  }
  if (nums1[i] < nums2[j]) {
    return false;
  }
  return compare(nums1, nums2, i + 1, j + 1);
}

function merge(nums1: number[], nums2: number[]): number[] {
  const m = nums1.length;
  const n = nums2.length;
  const ans: number[] = Array(m + n).fill(0);
  let i = 0;
  let j = 0;
  for (let k = 0; k < m + n; ++k) {
    if (compare(nums1, nums2, i, j)) {
      ans[k] = nums1[i++];
    } else {
      ans[k] = nums2[j++];
    }
  }
  return ans;
}