321. Create Maximum Number

题目链接：

这题就遍历所有可能的切分点n然后mergenums1[n]和nums2[k-n]求到最大值，nums1[n]和nums2[k-n]分别是nums1有n个数时候的最大值，和nums2有k-n个数时的最大值。merge部分比较简单，来看求最大值的部分。

设产生的最大值是max，max的size是n，num的size是m。现在已经选了了i个digit，最大值是max[0:i]，num用了j个数，现在指向num[j]。那么这就是用stack可以解决的问题了，如果stack的top元素小于num[j]且剩下的digits还够的话，那就一直pop，然后把num[j]放进栈顶，剩下的digits够的条件是：m - j >= n - i，所以可以pop的条件也就是：while(i > 0 && m - j > n - i && num[j] > max[i])

现在来确定切分点n的范围：0 <= n <= nums1.length并且0 <= k - n <= nums2.length，也就是k - num2.length <= n <= k，所以最后n的范围是：max(0, k-num2.length) <= n <= min(nums1.length, k)

merge的时候注意，如果两个array里面当前int相同，要比较它们之后的数字，选大的。

参考：

public class Solution {    public int[] maxNumber(int[] nums1, int[] nums2, int k) {        int[] global = new int[k];        if(k == 0) return global;                for(int n = Math.max(0, k-nums2.length); n <= Math.min(nums1.length, k); n++) {            int[] max1 = getLocalMax(nums1, n);            int[] max2 = getLocalMax(nums2, k-n);                    int[] temp = merge(max1, max2);            if(greater(temp, 0, global, 0)) global = temp;        }                return global;    }        private boolean greater(int[] a, int i, int[] b, int j) {        while(i < a.length && j < b.length) {            if(a[i] > b[j]) return true;            else if(a[i] < b[j]) return false;            i++; j++;        }        // equal is false        return i < a.length;    }        private int[] getLocalMax(int[] num, int n) {        int[] res = new int[n];        int m = num.length;        int i = 0;        for(int j = 0; j < m; j++) {            while(i > 0 && m - j > n - i && num[j] > res[i-1]) i--;            if(i < n) res[i++] = num[j];        }        return res;    }        private int[] merge(int[] num1, int[] num2) {        int n1 = num1.length, n2 = num2.length;        int[] res = new int[n1+n2];                int i = 0, j = 0;        for(int k = 0; k < res.length; k++) {            if(i >= n1) res[k] = num2[j++];            else if(j >= n2) res[k] = num1[i++];            else res[k] = greater(num1, i, num2, j) ? num1[i++] : num2[j++];        }        return res;    }}