321.拼接最大数

链接：321.拼接最大数
难度：Hard
标签：栈、贪心、数组、双指针、单调栈
简介：给定长度分别为  m  和  n  的两个数组，其元素由  0-9  构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n)  个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为  k  的数组。

题解 1 - typescript

• 编辑时间：2020-12-02
• 执行用时：228ms
• 内存消耗：48.7MB
• 编程语言：typescript
• 解法介绍：对于每个单调栈进行遍历。

function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
  const ans: number[][] = [];
  const pushArr = (nums: number[]) => {
    const len = nums.length;
    const arrLen = ans.length;
    const elLen = ans[0]?.length;
    if (arrLen === 0 || elLen === len) ans.push(nums);
    else if (elLen < len) {
      ans.length = 0;
      ans.push(nums);
    }
  };
  const getCache = (nums: number[], k: number): number[] => {
    const len = nums.length;
    const stack: number[] = [];
    if (k === 0) return stack;
    k = len - k;
    if (k <= 0) return nums;
    for (const num of nums) {
      if (stack.length === 0) {
        stack.push(num);
      } else {
        let top = stack[stack.length - 1];
        while (num > top && k !== 0) {
          stack.pop();
          k--;
          top = stack[stack.length - 1];
        }
        stack.push(num);
      }
    }
    while (k-- > 0) stack.pop();
    return stack;
  };
  for (let i = 0; i <= k; i++) {
    const stack1 = getCache(nums1, i);
    const stack2 = getCache(nums2, k - i);
    const len1 = stack1.length;
    const len2 = stack2.length;
    if (len1 === 0) pushArr(stack2);
    else if (len2 === 0) pushArr(stack1);
    else {
      const compare = (p1: number, p2: number): boolean =>
        p2 >= len2
          ? true
          : p1 >= len1
          ? false
          : stack1[p1] > stack2[p2]
          ? true
          : stack1[p1] < stack2[p2]
          ? false
          : compare(p1 + 1, p2 + 1);
      const arr: number[] = [];
      let i1 = 0;
      let i2 = 0;
      while (i1 !== len1 || i2 !== len2) {
        const num1 = stack1[i1];
        const num2 = stack2[i2];
        if (compare(i1, i2)) {
          arr.push(num1);
          i1++;
        } else {
          arr.push(num2);
          i2++;
        }
      }
      pushArr(arr);
    }
  }
  const len = ans[0].length;
  return ans.sort((nums1: number[], nums2: number[]) => {
    let i1 = 0;
    let i2 = 0;
    while (i1 < len && i2 < len) {
      const n1 = nums1[i1];
      const n2 = nums2[i2];
      if (n1 > n2) {
        return -1;
      } else if (n1 < n2) {
        return 1;
      } else {
        i1++;
        i2++;
      }
    }
    return 0;
  })[0];
}