class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] res = new int[0];
        for (int i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
            res = max(res, 0, merge(pick(nums1, i), pick(nums2, k - i)), 0);
        }
        return res;
    }

    private int[] max(int[] nums1, int i1, int[] nums2, int i2) {
        for (int i = i1; i < nums1.length; i++) {
            int j = i2 + i - i1;
            if (nums2.length <= j) return nums1;
            if (nums1[i] < nums2[j]) return nums2;
            if (nums2[j] < nums1[i]) return nums1;
        }
        return nums2;
    }

    private int[] pick(int[] nums, int k) {
        int[] res = new int[k];
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            while (0 < j && res[j - 1] < nums[i] && k <= (nums.length - i + j - 1)) j--;
            if (j < k) res[j++] = nums[i];
        }
        return res;
    }

    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] = max(nums1, i, nums2, j) == nums1 ? nums1[i++] : nums2[j++];
        return res;
    }
}