【LeetCode】321. 拼接最大数（贪心+单调栈类型题）

本文主要是介绍【LeetCode】321. 拼接最大数（贪心+单调栈类型题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在做帆软笔试的时候，最后一道题一直没想出来。

题目：在两个数组中选取 k 个元素，拼接一个最小数，并且要保证来自同一数组的元素顺序不发生改变。

搜索后发现是 LeetCode 321 拼接最大数的变形题，借此题学习一下。

402. 移掉 K 位数字（中等）

402. 移掉 K 位数字

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :
输入: num = “1432219”, k = 3
输出: “1219”
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = “10200”, k = 1
输出: “200”
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = “10”, k = 2
输出: “0”
解释: 从原数字移除所有的数字，剩余为空就是 0。

方法：贪心 + 单调栈

前置知识：对于两个数 123a456 和 123b456，如果 a > b，那么数字 123a456 大于数字 123b456，否则数字 123a456 小于等于数字 123b456。也就说，两个相同位数的数字大小关系取决于第一个不同的数的大小。

因此我们的思路就是：

考虑从左往右增量的构造最后的答案。用一个单调栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。根据之前的讨论：在使用 k 个删除次数之前，栈中的序列从栈底到栈顶单调不降。
对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到：
- 栈为空
- 或者新的栈顶元素不大于当前数字
- 或者已经删除了 k 位数字
如果删除了 m 个数字且 m<k，这种情况需要从序列尾部删除额外的 k−m 个数字。
如果最终的数字序列存在前导零，要删去前导零。
如果最终数字序列为空，我们应该返回 0。
最终，从栈底到栈顶的答案序列即为最小数。

class Solution {
public:string removeKdigits(string num, int k) {stack<char> st;for (int i = 0; i < num.size(); ++i) {if (!st.empty() && num[i] < st.top() && k > 0) {while (!st.empty() && num[i] < st.top() && k > 0) {st.pop();k--;                  }}st.push(num[i]);}while (k--) st.pop(); // 把末尾的数去除string ans;// 将栈的数弹出while (!st.empty()) {ans += st.top();st.pop();}reverse(ans.begin(), ans.end());// 去除前导 0int pos = 0;while (ans[pos] == '0') {pos++;}ans = ans.substr(pos, ans.size() - pos);return ans == "" ? "0" : ans;}
};

316. 去除重复字母

给一个字符串 s ，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = “bcabc”
输出：“abc”
示例 2：
输入：s = “cbacdcbc”
输出：“acdb”

与上面题目不同，这道题没有一个全局的删除次数 k。而是对于每一个在字符串 s 中出现的字母 c 都有一个 k 值。这个 k 是 c 出现次数 - 1。

所以，首先要计算每一个字符出现的次数。

具体算法：

建立一个哈希表，遍历字符串统计每一个字符 c 出现的剩余次数。
再建立一个存在数组exist，如果字符出现在栈里，就标记为true。
从左往右遍历字符串，每次遍历到一个字符，如果「它的字典序比前一个字典序更小」，且「前一个字符的剩余出现次数大于 1」，且「当前字符未在栈里」，可以将前一个字符弹出（丢弃），否则不可以丢弃。
考虑到栈的特点是后进先出，如果通过栈实现，则需要将栈内元素依次弹出然后进行翻转才能得到最小数。为了避免翻转操作，可以使用双端队列代替栈的实现。

class Solution {
public:string removeDuplicateLetters(string s) {vector<int> hash(26, 0);vector<bool> exist(26, false);for (char ch : s) {hash[ch - 'a']++;}string st;for (int i = 0; i < s.size(); ++i) {while (!st.empty() && s[i] < st.back() && hash[st.back() - 'a'] > 1 && !exist[s[i] - 'a']) {// 丢弃后需要更新状态 hash[st.back() - 'a'] -= 1;exist[st.back() - 'a'] = false;st.pop_back();}// 当前元素是否放入要看有没有出现在栈里if (exist[s[i] - 'a']) {hash[s[i] - 'a']--;continue;}st.push_back(s[i]);exist[s[i] - 'a'] = true;}return st;}
};

321. 拼接最大数

两个整数数组 nums1 和 nums2的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。
同时得到一个整数 k。利用这两个数组中的数字中创建一个长度为 k <= m + n 的最大数，必须保留来自同一数组的数字的相对顺序。
返回代表答案的长度为 k 的数组。
示例 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]

提示：

m == nums1.length
n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n

思路

和第一道题类似，不过这一次是两个数组，并且是求最大数。

最大最小是无关紧要的，关键在于是两个数组，并且要求从两个数组选取的元素个数加起来一共是 k。

在一个数组中取 k 个数字，并保持其最小（或者最大），我们已经会了。但是如果问题扩展到两个，会有什么变化呢？

实际上，问题本质并没有发生变化。假设从 nums1 中取了 k1 个，从 num2 中取了 k2 个，其中 k1 + k2 = k。而 k1 和 k2 这两个子问题我们是会解决的。由于这两个子问题是相互独立的，因此我们只需要分别求解，然后将结果合并即可。

假如 k1 和 k2 个数字，已经取出来了。那么剩下要做的就是将这个长度分别为 k1 和 k2 的数字，合并成一个长度为 k 的数组合并成一个最大的数组。

以题目的 nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 为例。假如我们从 num1 中取出 1 个数字，那么就要从 nums2 中取出 4 个数字。

运用第一题的方法，我们计算出应该取 nums1 的 [6]，并取 nums2 的 [9,5,8,3]。如何将 [6] 和 [9,5,8,3]，使得数字尽可能大，并且保持相对位置不变呢？

这个过程有点类似归并排序中的治，而分别计算 num1 和 num2 的最大数的过程类似归并排序中的分。

这里可以利用双指针，不断比较两个数组当前元素的大小，哪一个数字更大，就将其放入答案数组。如果相等，则比较两个剩余数组的字典序，选择更大字典序数组的首元素。

class Solution {
public:// 对数组 nums 删除 del 个元素vector<int> choose(vector<int>& nums, int del) {vector<int> ans;for (int i = 0; i < nums.size(); ++i) {while (ans.size() > 0 && nums[i] > ans.back() && del > 0) {ans.pop_back();del--;} ans.push_back(nums[i]);}while (ans.size() > 0 && del--) {ans.pop_back();}return ans;}// 将两个数组合并成一个值最大的数组vector<int> merge(vector<int>& nums1, vector<int>& nums2) {if (nums1 < nums2) swap(nums1, nums2);int p = 0,  q = 0;int len = nums1.size() + nums2.size();vector<int> ans(len);for (int i = 0; i < len; ++i) {if (p == nums1.size()) ans[i] = nums2[q++];else if (q == nums2.size()) ans[i] = nums1[p++];else {if (nums1[p] > nums2[q]) ans[i] = nums1[p++];else if (nums1[p] < nums2[q]) ans[i] = nums2[q++];else {vector<int> rest1(nums1.begin() + p, nums1.end());vector<int> rest2(nums2.begin() + q, nums2.end());if (rest1 > rest2) ans[i] = nums1[p++];else ans[i] = nums2[q++];}}}return ans;}vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {int len2 = nums2.size(), len1 = nums1.size();vector<int> result;// start 和 end 控制要从 nums1 中删除多少个元素int start = max(0, len1 - k), end = min(len1, len1 + len2 - k);for (int i = start; i <= end; ++i) {vector<int> vec1 = choose(nums1, i);vector<int> vec2 = choose(nums2, len1 + len2 - k - i);vector<int> temp = merge(vec1, vec2);result = max(result, temp); // vector可以直接比大小}return result;}
};