题目描述

321. Create Maximum Number

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

Example 1:

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]

Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

思路分析

为什么能使用单调栈？

本题其实是一道贪心算法题，在两个数组中按序找最大组合，它的最优子结构就是在每个数组中都按序找到最大组合。所以我们可以从每个数组的局部最优，推到全局最优。所以能使用单调栈。

为什么要使用单调栈？

这个问题是解决本题的关键，为什么要使用单调栈呢？本题要解决的问题简单来说就是在保证两个输入数组有序的前提下，找到一个最大的组合数。

所以我们要做的主要有两点：

1. 保证数组有序的前提下，找到每个数组最大的组合；
2. 保证两个数组有序的前提下，找到它们的最大拼接；

单调栈的特性，使得它能轻松地处理第一点。

这个单调栈不一般！

哪里不一般？显然是栈内元素数量，普通的单调栈无论是正序或是逆序，都是保证单调栈内元素全部有序，但是本题却不需要保证全部，为什么？答案很简单，我们给定的数量K是确定的，同时我们在循环遍历数组1，2时，每个数组要返回的vector大小也是固定的。所以当我们的单调栈只满足单调性时，元素数很可能不够！这时，我们就需要一些其他操作；

我们定义了一个遍历drop_num，这个是我们可以丢弃的元素数，一旦drop_num<=0之后，后面的元素都不允许我们丢弃了，简单来说就是返回的单调栈前面是有序的，后面可能无序（直接拼接）。

举个例子，假如我们给定的数组是【9，10，7，8，4，5，6】，我们要返回的数组大小是5，步骤如下图：

当我们丢弃了9，8 两个数之后，再丢弃元素就不够了，所以后面的都直接加入栈。

代码如下：

//求单调栈
vector<int> GetMonStack(vector<int> &nums,int length){
  stack<int> s;
  int n=nums.size();
  int drop_num=n-length;
  for(int i=0;i<n;++i){
    while(!s.empty() && s.top()<nums[i] && drop_num>0){
      s.pop();
      --drop_num;
    }
    if(s.size()<length)s.push(nums[i]);
    else --drop_num;
  }
  //把stack放到vector里返回
  return [](stack<int> ss){
    vector<int> res(ss.size(),0);
    int i=ss.size()-1;
    while(!ss.empty()){
      res[i--]=ss.top();
      ss.pop();
    }
    return res;
  }(s);
}

最后我们只需要遍历drop_num，选取最大值即可。这里我们可以遍历nums1数组所需的长度，那么nums2数组所需长度就是k-nums1.length。

num1所需最小长度就是min(0,k-nums2.length)(此时nums2全部都要了)，最大不能超过min(nums1.length,k)。

注意这里k可能要比任意一个数组长度要短。

int start=max(0,k-size_num2),end=min(size_num1,k);

单调栈合并 && 比较

得到了单调栈，我们要怎么把他们合并起来呢？假设单调栈内所有值代表的数字分别x和y，我们每次选取比较大数值那个数的首位做合并后数字的当前位即可。

选取比较大数值遵循以下比较步骤：

1. 比较当前元素大小，选择大的元素；
2. 如果一样大，比较后续元素；
3. 如此往复；

代码：

//比较函数
int compare(vector<int>& one, int index1, vector<int>& two, int index2) {
  int x = one.size(), y = two.size();
  while (index1 < x && index2 < y) {
    int tag = one[index1++] - two[index2++];
    if (tag != 0) return tag;
  }
  return (x - index1) - (y - index2);
}

//合并两个vector
vector<int> MergeVector(vector<int> &one,vector<int> &two){
  int size_one=one.size(),size_two=two.size();
  if(!size_one) return two;
  if(!size_two) return one;
  int a=0,b=0;
  int n=size_one+size_two,i=0;
  vector<int> res(size_one+size_two,0);
  while(i<n){
    if(compare(one,a,two,b)>0) res[i++]=one[a++];
    else res[i++]=two[b++];
  }
  return res;
}

代码

这里有个tips:由于单调栈内最终元素个数是确定的，为了减少数据搬运，我们直接使用vector<int>模拟栈行为。此时注意当len==0时候，单调栈内是没有数据的，要边界条件直接返回，防止下标溢出！

class Solution {
    vector<int> monoStack(vector<int>& nums, int len){
        //边界条件
        if(len==0) return vector<int>();
        int dropNum = nums.size() - len;
        vector<int> res(len,0);
        int top = -1;      
        for(int i = 0;i<nums.size();++i){
            while(top>=0&&res[top]<nums[i]&&dropNum>0){
                top--;
                dropNum--;
            }
            if(top < len - 1){ //top是下标，比模拟栈中的元素个数少1
                res[++top] = nums[i];
            }else{
                dropNum--;//超出最大长度，就不往栈里放数了。但是得继续循环，因为可能下一次会把栈顶元素pop()
            }
        }
        return res;
    }
    
    bool compare(vector<int>& one, int index1, vector<int>& two, int index2){
        int len1 = one.size();
        int len2 = two.size();
        while(index1<len1 && index2<len2){
            int diff = one[index1++] - two[index2++];
            if(diff!=0) return diff>0;
        }
        return (len1 - index1) > (len2 - index2);
    }

    vector<int> merge(vector<int>& one,vector<int>& two){
        int len1 = one.size();
        int len2 = two.size();
        //注意边界条件！
        if(len1==0) return two;
        if(len2==0) return one;
        vector<int> res(len1+len2,0);
        int index = 0, index1 = 0,index2 = 0;
        while(index<len1+len2){
            if(compare(one,index1,two,index2)){
                res[index++] = one[index1++];
            }else{
                res[index++] = two[index2++];
            }
        }
        return res;
    }
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        int start = max(0,k - len2);
        int end = min(len1,k);
        vector<int> res(k,0);
        for(int i = start;i<=end;++i){
            vector<int> t1(monoStack(nums1,i));
            vector<int> t2(monoStack(nums2,k-i));
            vector<int> tmp(merge(t1,t2));
            if(compare(tmp,0,res,0)) res.swap(tmp);
        }
        return res;
    }
};