package com.company;


import java.util.*;

// https://discuss.leetcode.com/topic/32272/share-my-greedy-solution/2

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] ret = new int[k];
        if (nums1.length + nums2.length < k) {
            return ret;
        }

        for (int i=Math.max(0, k-nums2.length); i<=k && i<= nums1.length; i++) {
            int[] tmp = merge(maxArr(nums1, i), maxArr(nums2, k-i));

            if (greater(tmp, 0, ret, 0)) {
                ret = tmp;
            }

        }
        return ret;
    }

    // 必须要有greater函数
    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]);
    }

    int[] merge(int[] nums1, int[] nums2) {
        int[] ret = new int[nums1.length + nums2.length];

        int t1 = 0;
        int t2 = 0;
        for (int i=0; i<ret.length; i++) {
            if (greater(nums1, t1, nums2, t2)) {
                ret[i] = nums1[t1++];
            }
            else {
                ret[i] = nums2[t2++];
            }
        }

        return ret;
    }

    int[] maxArr(int[] nums, int k) {
        int[] ret = new int[k];
        int j = 0;
        int len = nums.length;
        for (int i=0; i<len; i++) {
            while (j>0 && j+len-i>k && ret[j-1] < nums[i]) {
                j--;
            }
            if (j < k) {
                ret[j] = nums[i];
                j++;
            }
        }

        return ret;
    }


}

public class Main {

    public static void main(String[] args) throws InterruptedException {

        System.out.println("Hello!");
        Solution solution = new Solution();

        // Your Codec object will be instantiated and called as such:
        int[] nums1 = {6, 7};
        int[] nums2 = {6, 0, 4};
        int[] ret = solution.maxNumber(nums1, nums2, 5);
        for (int i=0; i<ret.length; i++) {
            System.out.printf("ret:%d\n", ret[i]);
        }
        System.out.println();

    }

}