拼接最大数

/*
 * Problem: Given two integer arrays nums1 and nums2, representing the digits of two numbers, 
 * and an integer k, find the maximum number of length k that can be formed from digits of nums1 and nums2, 
 * while maintaining the relative order of digits from each array.
 *
 * Approach: 
 * 1. Create a helper function to find the maximum subsequence of a given length from a single array using Streams.
 * 2. Iterate over all possible lengths for subsequences from both arrays such that their combined length is k.
 * 3. Merge the two subsequences to form the largest possible number.
 * 4. Compare the merged number with the current maximum and update if necessary.
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class SolutionStream {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        int[] maxSubsequence = new int[k];
        for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
            int[] subsequence1 = maxSubsequence(nums1, i);
            int[] subsequence2 = maxSubsequence(nums2, k - i);
            int[] candidate = merge(subsequence1, subsequence2);
            if (greater(candidate, 0, maxSubsequence, 0)) {
                maxSubsequence = candidate;
            }
        }
        return maxSubsequence;
    }

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

    private int[] merge(int[] nums1, int[] nums2) {
        return IntStream.concat(IntStream.of(nums1), IntStream.of(nums2))
                        .boxed()
                        .sorted((a, b) -> b - a)
                        .mapToInt(i -> i)
                        .toArray();
    }

    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]);
    }
}