leetcode321.拼接最大数

题目链接

综合度挺高的一道题，设计到单调栈，数组合并，分治等等

①首先两个数组拼成一个长度为K的数组，所以可以从nums1从取0~K个数，同时在nums2中取K~0个数，这块和leetcode402基本一致，在nums1中取K个数相当于删除nums1.length - K个数的最大组合

②把取出来的两个数组合并起来，主要在于相同值的处理，如果当前值相同话，就要比较下一位，而当某一个数组A的最后一位都和另一个数组B数值相同，那么就要转换一下，比较A的起始值和B的当前值来保证组合的数字是最大的！

③最后就是将每次的值和最大值作比较，取大即可

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] res = new int[k];
        for (int i = 0; i <= k; i++) {
            if (i > nums1.length || k - i > nums2.length) {
                continue;
            }           
            int[] res1 = maxK(nums1, i);
            int[] res2 = maxK(nums2, k - i);
            int[] merge = merge(res1, res2);
            res = compare(res, merge);
        }
        return res;
    }

    public int[] maxK(int[] num, int k) {
        int len = num.length;
        int[] res = new int[k];
        if (k == 0) {
            return res;
        }       
        int delNum = len - k;
        Stack stack = new Stack<>();

        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && num[i] > num[stack.peek()] && delNum > 0) {
                delNum--;
                stack.pop();
            }
            stack.push(i);
        }

        while (delNum > 0) {
            stack.pop();
            delNum--;
        }

        for (int i = k - 1; i >= 0; i--) {
            res[i] = num[stack.pop()];
        }
        return res;
    }

    public int[] merge(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] res = new int[len1 + len2];
        int p = 0;
        int q = 0;
        for (int i = 0; i < len1 + len2; i++) {
            if (p < len1 && q < len2) {
                int a = p;
                int b = q;
                while (a < len1 && b < len2 && nums1[a] == nums2[b]) {
                    if (a < len1 - 1 && b < len2 - 1) {
                        a++;
                        b++;
                    } else if (a < len1 - 1 && b == len2 - 1) {
                        a++;
                        b = q;
                    } else if (a == len1 - 1 && b < len2 - 1){
                        b++;
                        a = p;
                    } else {
                        break;
                    }
                }
                res[i] = nums1[a] > nums2[b] ? nums1[p++] : nums2[q++];
            } else if (p < len1) {
                res[i] = nums1[p++];
            } else {
                res[i] = nums2[q++];
            }
        }
        return res;
    }

    public int[] compare(int[] nums1, int[] nums2) {
        for (int i = 0; i < nums2.length; i++) {
            if (nums1[i] > nums2[i]) {
                return nums1;
            } else if (nums1[i] < nums2[i]) {
                return nums2;
            }
        }
        return nums1;
    }
}