🌕🌕 321. 拼接最大数

难度: 🌕🌕

问题描述

---

解法

class Solution {
    int[] res;
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        // 思路：
        // 1. 从 nums1[] 中取出 i 个数，从 nums2[] 中取出 j 个数，取出的数分别是能形成的当前个数的最大数
        // 通过 单调栈 的方式实现
        // 2. 对于 nums1[i] & nums2[j] 进行合并，得到 arr[i + j] = arr[k]
        // 3. 对于当前 arr[k] 判断是否是所有情况中最大的，从而更新 res

        int m = nums1.length;
        int n = nums2.length;
        res = new int[k];

        for(int i = 0; i <= m && i <= k; i ++) {
            int j = k - i;
            if(j <= n) {
                int[] aa = getMax(nums1, i);
                int[] bb = getMax(nums2, j);
                int[] tmpArr = merge(aa, bb);
                if(compareFromIndex(tmpArr, 0, res, 0)) {
                    res = tmpArr;
                }
            }
        }
        return res;
    }

    private boolean compareFromIndex(int[] aa, int a, int[] bb, int b) {
        // 若 aa > bb 返回 true
        if(a >= aa.length) {
            return false; // 前面都相等，那么后面的数位数多，因此 aa < bb
        }
        if(b >= bb.length) {
            return true;
        }
        if(aa[a] > bb[b]) {
            return true;
        } else if(aa[a] < bb[b]) {
            return false;
        } else {
            return compareFromIndex(aa, a + 1, bb, b + 1);
        }
    }

    private int[] merge(int[] aa, int[] bb) {
        // 合并数组
        int len = res.length;
        int[] tmpArr = new int[len];
        int index = 0;

        int la = aa.length;
        int lb = bb.length;
        int i = 0;
        int j = 0;

        while(i < la || j < lb) {
            if(compareFromIndex(aa, i, bb, j)) {
                tmpArr[index] = aa[i];
                i ++;
            } else {
                tmpArr[index] = bb[j];
                j ++;
            }
            index ++;
        }
        return tmpArr;
    }

    private int[] getMax(int[] arr, int count) {
        // 单调栈，从 arr[] 中取出 count 个数
        // 由于 栈 的大小固定，因此可以使用 数组 实现
        // System.out.println(Arrays.toString(arr) + "  " + count);
        int[] stack = new int[count];
        if(count == 0) {
            return stack;
        }
        int len = arr.length;
        int rm = len - count; // 需要删除的元素个数
        int peekIndex = -1;

        int i = 0;
        for(; i < len; i ++) {
            int cur = arr[i];
            if(peekIndex < 0 || cur < stack[peekIndex]) {
                if(peekIndex < count - 1) {
                    peekIndex ++;
                    stack[peekIndex] = cur;
                } else {
                    rm --; // 数组放不下这个数，只能删除
                }
            } else if(cur == stack[peekIndex]) {
                if(peekIndex < count - 1) {
                    peekIndex ++;
                    stack[peekIndex] = cur;
                } else {
                    rm --;
                }
            } else {
                // cur > stack.peekLast() 需要弹栈 - 删除栈顶元素 - 换成更大的数
                while(rm > 0 && peekIndex >= 0 && cur > stack[peekIndex]) {
                    peekIndex --;
                    rm --;
                }
                if(rm == 0) {
                    break;
                } 
                if(peekIndex < count - 1) {
                    peekIndex ++;
                    stack[peekIndex] = cur;
                }
            }
        }

        // 只有当 rm == 0 而 stack 还未填充满，剩下的数字均需保留时，才会进入下面的循环
        while(peekIndex < count - 1) {
            peekIndex ++;
            stack[peekIndex] = arr[i];
            i ++;
        }
        // System.out.println(Arrays.toString(stack) + "  " + count);
        // System.out.println();
        return stack;
    }
}

---

输出