拼接最大数

发表于
本文字数： 3.5k 阅读时长 ≈ 3 分钟

LeetCode每日一题，321. Create Maximum Number

先看题目描述

DINaHU.png

大意就是给定长度分别为 m 和 n 的两个数组，数组中的元素只含 0 - 9，再给定一个 k，让我们从这两个数组中选出 k 个数字拼接成一个新的数，要求从同一个数组中取出的数相对顺序不变，让我们找出满足该条件的最大数

算法和思路

这题是上个月的每日一题 移掉k位数字 的升级版，思路一会就想到了，但在合并两个子序列得到最大数的过程中出现了问题，看了题解代码才知道如何解决

贪心+单调栈

为了找到长度为 k 的最大数，需要从两个数组中分别选出最大的子序列，这两个子序列的长度之和为 k，然后将这两个子序列合并得到最大数。两个子序列的长度最小为 0，最大不能超过 k 且不能超过对应的数组长度

令数组 nums1 的长度为 m，nums2 的长度为 n，则需要从 nums1 中选出长度为 x 的子序列，从 nums2 中选出长度为 y 的子序列，其中 x + y = k，且满足 0 ≤ x ≤ m 和 0 ≤ y ≤ n。需要遍历所有可能的 x 和 y 的值，对于每一组 x 和 y 的值，得到最大数。在整个过程中维护可以通过拼接得到的最大数

对于每一组 x 和 y 的值，得到最大数的过程分成两步，第一步是分别从两个数组中得到指定长度的最大子序列，第二步是将两个最大子序列合并

第一步可以通过贪心算法和单调栈实现。单调栈满足从栈底到栈顶的元素单调递减，从左到右遍历数组，遍历过程中维护单调栈内的元素，需要保证遍历结束之后单调栈内的元素个数等于指定的最大子序列的长度。遍历结束之后，将从栈底到栈顶的元素依次拼接，即得到最大子序列

第二步需要自定义比较方法。首先比较两个子序列的当前元素，如果两个当前元素不同，则选其中较大的元素作为下一个合并的元素，否则需要比较后面的所有元素才能决定选哪个元素作为下一个合并的元素

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.*;

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int start = Math.max(0, m - k);
        int end = m + n - k - Math.max(0, n - k);
        int[] res = new int[k];
        for (int i = start; i <= end; i++) {
            int[] temp1 = maxNumInOneArray(nums1, i);
            int[] temp2 = maxNumInOneArray(nums2,  m + n - k - i);
            int[] temp = new int[k];
            int index = 0;
            int p1 = 0;
            int p2 = 0;
            while (index < k) {
                if (p1 >= temp1.length) {
                    temp[index] = temp2[p2];
                    p2++;
                } else if (p2 >= temp2.length) {
                    temp[index] = temp1[p1];
                    p1++;
                } else {
                    if (compare(temp1, p1, temp2, p2) >= 0) {
                        temp[index] = temp1[p1];
                        p1++;
                    } else {
                        temp[index] = temp2[p2];
                        p2++;
                    }
                }
                index++;
            }
            if (compare(temp, 0, res, 0) > 0) {
                System.arraycopy(temp, 0, res, 0, k);
            }
        }
        return res;
    }

    private int[] maxNumInOneArray(int[] nums, int k) {
        if (k == 0) return nums;
        int len = nums.length;
        if (len == k) return new int[]{};
        int[] res = new int[len - k];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            while (k > 0 && !deque.isEmpty() && num > deque.peekLast()) {
                deque.removeLast();
                k--;
            }
            deque.add(num);
        }
        while (k > 0) {
            deque.removeLast();
            k--;
        }
        for (int i = 0; i < res.length; i++) {
            res[i] = deque.removeFirst();
        }
        return res;
    }

    private int compare(int[] nums1, int index1, int[] nums2, int index2) {
        int m = nums1.length;
        int n = nums2.length;
        while (index1 < m && index2 < n) {
            int diff = nums1[index1] - nums2[index2];
            if (diff != 0) return diff;
            index1++;
            index2++;
        }
        return (m - index1) - (n - index2);
    }
}

ps：自己一开始没看题解做题时，从两个数组中得到指定长度的最大子序列这一步没问题，但将两个最大子序列合并这一步一直出问题，没想到要自己自定义一个比较的方法，看了题解以后才明白需要自定义一个比较的方法