Ming
0%

LeetCode-321

Posted on Edited on In

题目

Snipaste_2020-12-02_16-44-03.png

结果

Snipaste_2020-12-02_17-27-59.png

Snipaste_2020-12-02_17-28-04.png

代码

这题很复杂（I think），但不是数学的那种复杂，我写了好久。

这题可以大概划分为几个步骤，每个步骤可以当做一个小题来做了。

  1. 从第一个数组里挑X个，第二个数组里挑Y个，有哪几种挑选方案？
  2. 将两个数组拼接成一个数组，使得最终结果数值最大，元素在原数组中的相对位置不变。
  3. 从一堆数组里选出数值最大的。
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int x = 0, y = k;
        List<int[]> list = new LinkedList<>();
        for (int i = 0; i <= k; i++, x++, y--) {
            if (x <= nums1.length && y <= nums2.length) {
                list.add(merge(maxSubsequence(nums1, x), maxSubsequence(nums2, y)));
            }
        }

        // 返回所有结果中最大的
        return list.stream().max(this::cmp).get();
    }

    // 返回给定数组长度为length的最大子序列
    private int[] maxSubsequence(int[] nums, int k) {
        Deque<Integer> stack = new LinkedList<>();
        // 选择的余地
        int behind = nums.length - k;
        for (int num : nums) {
            while (!stack.isEmpty() && stack.peek() < num && behind > 0) {
                stack.pop();
                behind--;
            }
            if (stack.size() < k) {
                stack.push(num);
            } else {
                behind--;
            }
        }
        // 需要正向（从栈底到栈顶）遍历stack
        List<Integer> list = new ArrayList<>(stack);
        Collections.reverse(list);
        int[] ans = new int[k];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    // 合并两个数组，使结果数值最大
    private int[] merge(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length + nums2.length];
        int index1 = 0, index2 = 0;
        for (int i = 0; i < ans.length; i++) {
            // 先添加哪个数组的元素呢？（哪个大添加哪个，但如果一样大还需要考虑后面元素的大小）
            int flag = cmp(nums1, index1, nums2, index2);
            if (flag < 0) {
                ans[i] = nums2[index2];
                index2++;
            } else {
                ans[i] = nums1[index1];
                index1++;
            }
        }
        return ans;
    }

    // 重载只为方便主函数调用
    private int cmp(int[] nums1, int[] nums2) {
        return cmp(nums1, 0, nums2, 0);
    }

    // 从指定位置开始逐位比较两个数组的大小
    private int cmp(int[] nums1, int index1, int[] nums2, int index2) {
        // 因为cmp的递归，存在越界的情况
        if (index1 >= nums1.length) {
            if (index2 >= nums2.length) {
                return 0;
            } else {
                return -1;
            }
        }
        if (index2 >= nums2.length) {
            if (index1 >= nums2.length) {
                return 0;
            } else {
                return 1;
            }
        }

        if (nums1[index1] < nums2[index2]) {
            return -1;
        } else if (nums1[index1] == nums2[index2]) {
            // 递归
            return cmp(nums1, index1 + 1, nums2, index2 + 1);
        } else {
            return 1;
        }
    }
}

复杂度

Have a good time!