题目来源

• leetcode：321. 拼接最大数

题目描述

class Solution {
    
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    

    }
};

题目解析

题意

这道题给了我们两个数组，里面的数字是无序的，又给我们一个k值并且k <= n1 + n2，要求我们从两个数组中跳出k个数，数字之间的相对顺序不变，求能组成的最大的数

单调栈

为什么可以使用单调栈？

• 本题的本质即为从两个数组中挑选k个元素，并且使得拼接后的字典序最大。
• 要使得数组的字典序最大，则需要保证从左到右的每一个位置的值尽可能的大，即单调递减

思路：

• 可以枚举所有k的组合情况，分别从两个数组中取i、j个元素构成的最大数组，然后再进行合并，最终保留最大值
• 在挑选指定个数的元素的过程中，分别从两个数组中取i、j个元素构成的最大数组，然后再进行合并，最终保留最大值

问题： 枚举所有k的组合情况？

由于k的大小不定，所以有三种可能：

• 第一种是当k为0时，两个数组中都不取数。
• 第二种是当k不大于其中任意一个数组的长度时，这种情况下，有可能只从一个数组中取数，或者两个都取一些。
• 第三种情况是k大于其中任意一个数组的长度，则需要从两个数组中分别取数，至于每个数组中取几个，每种情况都要考虑到，然后每次更结果即可。

为了同时能处理这三种情况，这里假设从数组 nums1 中取i个数，那么就需要从 nums2 中取 k-i 个数。那么i的范围如何确定呢？

• 怎么确定i的起始范围？
  • 由情况二的得出：可以不从nums1中取数，所以i最小值为0
  • 由情况三的得出：假如所有数均从nums2中取&&k > len(nums2)，那么剩下的k - size2数必须从nums1取。
  • 综上，i的起始范围为std::max(0, k - size2)
• 怎么确定i的结束范围？也就是i最大能多大
  • 如果k <= size1，那么最大能从nums1中取k个
  • 如果k > size1，那么最大能从nums1中取size1个
  • 综上，i的结束范围为std::min(k, size1);

怎么一个数组挑选出最大的组合？

• 比如当前数组长度为n，需要取出k个数字，那么需要对掉drop = n - k个数字
• 遍历数组中的数字，进行如下循环： 如果此时drop > 0 && ans不为空 && ans.back < curr，那么丢弃ans并drop-+ 重复循环直至上述任意条件不满足为止，然后把当前元素加入结果数组中
• 最后返回ans数组中的前k个元素

现在分别从 nums1 中取出了i个最大组合的数字，从 nums2 中取出了 k-i 个最大组合的数字，怎么合并呢？

• 先比较两个元素中首部元素大小
• 然后从当前比较大的数组中取头一个元素
• 然后删除头部元素
• …接着比较，直到两个数组都为空停止

class Solution {
    
    std::vector<int> mergeVector(vector<int>& nums1, vector<int>& nums2){
    
        std::vector<int> ans;
        while (!nums1.empty()  || !nums2.empty()){
    
            vector<int> &tmp =(nums1 > nums2) ? nums1 : nums2;
            ans.push_back(tmp[0]);
            tmp.erase(tmp.begin());
        }
        return ans;
    }
    // 从nums中挑选k个数
    std::vector<int> maxVector(vector<int>& nums, int k){
    
        int drop = (int) nums.size() - k;
        std::vector<int> ans;
        for(int num : nums){
    
            while (drop > 0 && !ans.empty() && ans.back() < num){
    
                ans.pop_back();
                --drop;
            }
            ans.push_back(num);
        }
        ans.resize(k);
        return ans;
    }
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    
        int size1 = nums1.size(), size2 = nums2.size();
        std::vector<int> ans;
        int start = std::max(0, k - size2);
        int end = std::min(k, size1);
        for (int i = start; i <= end; ++i) {
      // 最多可以从nums1中选end个数
            auto pick1 = maxVector(nums1, i);
            auto pick2 = maxVector(nums2, k - i);
            ans = std::max(ans, mergeVector(pick1, pick2));
        }
        return ans;
    }
};
int main() {
    
    vector<int> nums1 {
    3, 4, 6, 5};
    vector<int> nums2 {
    9, 1, 2, 5, 8, 3};
    Solution a;
    auto ans = a.maxNumber(nums1, nums2, 5);
    for(auto i : ans){
    
        printf("%d\t", i);
    }


    return 0;
}

类似题目

• 316. 去除重复字母
• 402. 移掉 K 位数字
  • 核心思路与402. 移掉 K 位数字一样，使用单调栈获取最大数字。
  • 不一样的是，402题是一个数组，且要移除的次数确定，321题是「两个数组」，移除的次数「不确定」
• 670. Maximum Swap 最大置换