Skip to content

321. Create Maximum Number 👍

  • Time: $O(k(m + n)^2)$
  • Space: $O(m + n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<int> ans;

    for (int k1 = 0; k1 <= k; ++k1) {
      const int k2 = k - k1;
      if (k1 > nums1.size() || k2 > nums2.size())
        continue;
      ans = max(ans, merge(maxArray(nums1, k1), maxArray(nums2, k2)));
    }

    return ans;
  }

 private:
  vector<int> maxArray(const vector<int>& nums, int k) {
    vector<int> res;
    int toPop = nums.size() - k;
    for (const int num : nums) {
      while (!res.empty() && res.back() < num && toPop-- > 0)
        res.pop_back();
      res.push_back(num);
    }
    return {res.begin(), res.begin() + k};
  }

  // Merges nums1 and nums2.
  vector<int> merge(const vector<int>& nums1, const vector<int>& nums2) {
    vector<int> res;
    auto s1 = nums1.cbegin();
    auto s2 = nums2.cbegin();
    while (s1 != nums1.cend() || s2 != nums2.cend())
      if (lexicographical_compare(s1, nums1.cend(), s2, nums2.cend()))
        res.push_back(*s2++);
      else
        res.push_back(*s1++);
    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
  public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int[] ans = new int[k];

    for (int k1 = 0; k1 <= k; ++k1) {
      final int k2 = k - k1;
      if (k1 > nums1.length || k2 > nums2.length)
        continue;
      int[] candidate = merge(maxArray(nums1, k1), maxArray(nums2, k2));
      if (greater(candidate, 0, ans, 0))
        ans = candidate;
    }
    return ans;
  }

  private int[] maxArray(int[] nums, int k) {
    List<Integer> res = new ArrayList<>();
    int toPop = nums.length - k;
    for (final int num : nums) {
      while (!res.isEmpty() && res.get(res.size() - 1) < num && toPop > 0) {
        res.remove(res.size() - 1);
        --toPop;
      }
      res.add(num);
    }
    return res.subList(0, k).stream().mapToInt(i -> i).toArray();
  }

  // Merges nums1 and nums2.
  private int[] merge(int[] nums1, int[] nums2) {
    int[] res = new int[nums1.length + nums2.length];
    for (int i = 0, j = 0, k = 0; k < res.length; ++k)
      res[k] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
    return res;
  }

  // Returns true if nums1[i..n) > nums2[j..n).
  private boolean greater(int[] nums1, int i, int[] nums2, int j) {
    while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
      ++i;
      ++j;
    }
    return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def maxNumber(self, nums1: list[int], nums2: list[int], k: int) -> list[int]:
    def maxArray(nums: list[int], k: int) -> list[int]:
      res = []
      toTop = len(nums) - k
      for num in nums:
        while res and res[-1] < num and toTop > 0:
          res.pop()
          toTop -= 1
        res.append(num)
      return res[:k]

    def merge(nums1: list[int], nums2: list[int]) -> list[int]:
      return [max(nums1, nums2).pop(0) for _ in nums1 + nums2]

    return max(merge(maxArray(nums1, i), maxArray(nums2, k - i))
               for i in range(k + 1)
               if i <= len(nums1) and k - i <= len(nums2))