leetcode

0 class Solution {

1 static bool greater(const vector<int> &nums1, const vector<int> &nums2, int i, int j) {

2 while (i < size(nums1) && j < size(nums2) && nums1[i] == nums2[j])

3 i++, j++;

4 return j == size(nums2) || (i < size(nums1) && nums1[i] > nums2[j]);

5 }

6

7 static vector<int> merge(const vector<int> &nums1, const vector<int> &nums2, int k) {

8 vector<int> res(k);

9

10 for (int i = 0, j = 0, l = 0; l < k; l++) {

11 res[l] = greater(nums1, nums2, i, j) ? nums1[i++] : nums2[j++];

12 }

13

14 return res;

15 }

16

17 static vector<int> maxArr(const vector<int> &nums, int k) {

18 const int n = size(nums);

19 vector<int> res(k);

20

21 for (int i = 0, j = 0; i < n; i++) {

22 while (n - i + j > k && j > 0 && res[j - 1] < nums[i])

23 j--;

24 if (j < k) res[j++] = nums[i];

25 }

26

27 return res;

28 }

29

30 public:

31 vector<int> maxNumber(const vector<int> &nums1, const vector<int> &nums2, int k) const {

32 const int n = size(nums1), m = size(nums2);

33 vector<int> res(k);

34

35 for (int i = max(0, k - m); i <= k && i <= n; i++) {

36 const auto candid = merge(maxArr(nums1, i), maxArr(nums2, k - i), k);

37 res = max(res, candid);

38 }

39

40 return res;

41 }

42 };