Luobuyu's Blog

0%

321.拼接最大数

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.1k 阅读时长 ≈ 2 分钟
使用单调栈拼接，注意合并时候的比较大小。

321.拼接最大数

题目描述：

给出两个长度分别为 $m$ 和 $n$ 的数组，其元素由 0-9组成。现在从这两个数组中选出 $k$ 个数字拼接成一个新的数字，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

数据范围：
$1\le k \le m + n$

题解：

使用单调栈维护两个单调减的栈，合起来长度为 $k$ 。枚举两个数组中长度 $l1,l2$ ，其中 $l1 + l2 = k$ 。需要注意的是，如果当前栈中的元素数量加上剩余的元素的数量大于 $k$ 时才能出栈，否则只能把剩余的都加进来。

合并时类似归并排序合并，如果两个数字不相等，则选大的加入；如果相等需要根据后续的数字判断，例如：

$num1$ ：[6, 7]

$num2$ ：[6, 0, 4]

$k = 5$

合并时，最大的为 $[6, 7, 6, 0, 4]$ ，相等时需要看后续的，后续哪个大选哪个，如果全一样，哪个短选哪个（哪个长选哪个也对）。

代码：

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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    // 从 num 中取出 k 个数，最大
    vector<int> getSeq(vector<int> &num, int k)
    {
        vector<int> st(k);
        int top = -1, remain = num.size();
        for (int i = 0; i < num.size(); ++i)
        {
            while (top >= 0 && top + 1 + remain > k && st[top] < num[i])
            {
                --top;
            }
            --remain;
            if (top + 1 < k)
                st[++top] = num[i];
        }
        return st;
    }
    // 合并
    vector<int> merge(vector<int> &nums1, vector<int> &nums2)
    {
        int l1 = 0, l2 = 0;
        int m = nums1.size(), n = nums2.size();
        if (m == 0)
            return nums2;
        if (n == 0)
            return nums1;
        vector<int> ret;
        ret.reserve(m + n);
        while (l1 < m && l2 < n)
        {
            if (cmp(nums1, nums2, l1, l2))
                ret.emplace_back(nums1[l1++]);
            else
                ret.emplace_back(nums2[l2++]);
        }
        while (l1 < m)
            ret.emplace_back(nums1[l1++]);
        while (l2 < n)
            ret.emplace_back(nums2[l2++]);
        return ret;
    }
    vector<int> maxNumber(vector<int> &nums1, vector<int> &nums2, int k)
    {
        int m = nums1.size(), n = nums2.size();
        int l = max(0, k - n), r = min(m, k);
        vector<int> seq1, seq2, seq;
        vector<int> ans(k, 0);
        for (int i = l; i <= r; ++i)
        {
            seq1 = getSeq(nums1, i);
            seq2 = getSeq(nums2, k - i);
            seq = merge(seq1, seq2);
            if (cmp(seq, ans, 0, 0))
            {
                ans = seq;
            }
        }
        return ans;
    }
    bool cmp(vector<int> &nums1, vector<int> &nums2, int l1, int l2)
    {
        int m = nums1.size(), n = nums2.size();
        int i = l1, j = l2;
        while (i < m && j < n)
        {
            if (nums1[i] != nums2[j])
                return nums1[i] > nums2[j];
            i++;
            j++;
        }
        return m - l1 > n - l2;
    }
};