題目鏈接

Leetcode.321 拼接最大數(shù) hard

題目描述

給定長(zhǎng)度分別為 $m$ 和 $n$ 的兩個(gè)數(shù)組，其元素由 $0～9$ 構(gòu)成，表示兩個(gè)自然數(shù)各位上的數(shù)字?，F(xiàn)在從這兩個(gè)數(shù)組中選出 $k$ $(k\le m+n)$ 個(gè)數(shù)字拼接成一個(gè)新的數(shù)，要求從同一個(gè)數(shù)組中取出的數(shù)字保持其在原數(shù)組中的相對(duì)順序。

求滿足該條件的最大數(shù)。結(jié)果返回一個(gè)表示該最大數(shù)的長(zhǎng)度為 $k$ 的數(shù)組。

說(shuō)明: 請(qǐng)盡可能地優(yōu)化你算法的時(shí)間和空間復(fù)雜度。

示例 1:

輸入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
輸出:
[9, 8, 6, 5, 3]

示例 2:

輸入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
輸出:
[6, 7, 6, 0, 4]

示例 3:

輸入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
輸出:
[9, 8, 9]

解法：單調(diào)棧

我們假設(shè)由 $k$ 個(gè)元素組成的最大數(shù)，其中有 $x$ 個(gè)元素來(lái)自 $nums1$，那么就有 $k?x$ 個(gè)元素來(lái)自 $nums2$。

我們定義 $max\_sequence(S,m)$ 表示從集合 $S$ 中，選出 $m$ 個(gè)元素構(gòu)成的最大數(shù)（元素之間要保持在集合 $S$ 中的相對(duì)位置）。

• $s1=max\_sequence(nums1,x)$，$s1$ 表示從集合 $nums1$ 中選出 $x$ 個(gè)元素組成的最大數(shù)；
• $s2=max\_sequence(nums2,k?x)$，$s2$ 表示從集合 $nums2$ 中選出 $k?x$ 個(gè)元素組成的最大數(shù)；

我們最后再將 $s1$ 和 $s2$ 拼接成一個(gè)最大數(shù) $S$，那么這個(gè) $S$ 就是答案之一。所以我們就要遍歷 $x$ ，求出所有的 $S$，最后返回最大的那個(gè)。

在實(shí)現(xiàn)上：

$max\_sequence(S,m)$ 可以利用單調(diào)棧實(shí)現(xiàn)：

• 如果 $S.size()\le m$，那么直接返回集合 $S$ 即可；
• 我們定義一個(gè)棧 $stk$，因?yàn)槲覀円祷氐氖?$m$ 個(gè)元素組成的最大數(shù)，也就是說(shuō) $stk$ 最終有 $m$ 個(gè)元素，即 $stk$ 能夠彈出去的元素最多只有 $del=S.size()?m$ 個(gè)。
• 假設(shè)當(dāng)前遍歷到的元素為 $x$，如果 $x>stk.top()$ 并且 $del>0$，那么就可以彈出棧頂元素，因?yàn)槲覀円?span id="vxwlu0yf4" class="katex--inline">$stk$ 中的數(shù)字典序盡可能的大。
• 最終返回 $stk$ 即可。需要注意的是：如果 $S$ 中所有元素都相同 或者 $S$ 是一個(gè)非降序的序列，那么 $stk$ 中就沒(méi)有彈出的元素，一共就有 $S.size()$ 個(gè)元素，我們只需要前 $m$ 個(gè)即可。

在這里需要介紹一個(gè) STL algorithm 庫(kù)的函數(shù) lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)

template<class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2)
{for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2){if (*first1 < *first2)return true;if (*first2 < *first1)return false;}return (first1 == last1) && (first2 != last2);
}

上述這個(gè)函數(shù)的作用是：判斷區(qū)間一 $[first1,last1)$ 字典序是否不大于 區(qū)間二$[first2,last2)$。

• 是的話，最終返回 true；
• 否，返回 false；

時(shí)間復(fù)雜度： $O(m+n+k^2)$

C++代碼：

class Solution {
public:vector<int> max_sequence(vector<int> vec,int k){int n = vec.size();if(n <= k) return vec;vector<int> stk;int del = n - k;for(int i = 0;i < n;i++){while(stk.size() && vec[i] > stk.back() && del){del--;stk.pop_back();}stk.push_back(vec[i]);}stk.resize(k);return stk;}vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {int m = nums1.size() , n = nums2.size();vector<int> res(k,0);for(int x = max(0,k - n);x <= min(k,m);x++){vector<int> temp;auto s1 = max_sequence(nums1,x);auto s2 = max_sequence(nums2,k - x);auto it1 = s1.begin() , it2 = s2.begin();while(it1 != s1.end() || it2 != s2.end()){temp.push_back(lexicographical_compare(it1,s1.end(),it2,s2.end() )? *it2++ : *it1++);}res = lexicographical_compare(res.begin(),res.end(),temp.begin(),temp.end()) ? move(temp) : res;}return res;}
};