LeetCode 316. 去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"
输出："abc"示例 2：
输入：s = "cbacdcbc"
输出："acdb"method：单调栈
先记录每个字母出现的最后位置
如果当前字母比前面的字母小，并且前面的字母在后面又会出现，那肯定要取后面出现的那个，才能保证字典序最下
如果一个字母已经在栈中，后面就不用再考虑了，前面已经保证是最小字典序了
string removeDuplicateLetters(string s) {
int nums[26] = {-1};
int n = s.size();
for (int i = 0; i < n; i++) {
nums[s[i] - 'a'] = i;
}
bool used[26] = {false};
string st; // 用字符串当栈，后面就不用再转移了
for (int i = 0; i < n; i++) {
if (used[s[i] - 'a']) continue;
while (!st.empty() && s[i] < st.back() && nums[st.back() - 'a'] > i) {
used[st.back() - 'a'] = false;
st.pop_back();
}
st.push_back(s[i]);
used[s[i] - 'a'] = true;
}
return st;
}时间复杂度：$O(n)$
空间复杂度：$O(n)$
LeetCode 402. 移掉 K 位数字
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 ：
输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。示例 2 ：
输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。method: 栈
类似地，如果当前数字比栈顶数字小，就一直把栈顶数字弹出，最多进行k次
如果k没用完，就继续用，已经是最小字典序，就直接从后面弹出
还要去掉前面的0
string removeKdigits(string num, int k) {
string st;
for (auto ch : num) {
while (!st.empty() && ch < st.back() && k) {
st.pop_back();
k--;
}
st.push_back(ch);
}
while (!st.empty() && k-- > 0) st.pop_back();
string res = "";
bool isLeadingZero = true;
for (auto s : st) {
if (isLeadingZero && s == '0') continue;
isLeadingZero = false;
res.push_back(s);
}
return res.empty() ? "0" : res;
}时间复杂度：$O(n)$
空间复杂度：$O(n)$
LeetCode 321. 拼接最大数
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 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]method
分别从nums1里面取x个组成最大排序，从nums2里面取y个组成最大排序，且x+y=k
然后合并两个最大排序
vector<int> getKElem(vector<int>& nums, int k) {
int n = nums.size() - k;
vector<int> st;
for (auto num : nums) {
while (!st.empty() && num > st.back() && n) {
st.pop_back();
n--;
}
st.push_back(num);
}
while (!st.empty() && n--) st.pop_back();
return st;
}
vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if (m == 0) return nums2;
if (n == 0) return nums1;
vector<int> res(m + n);
int index1 = 0, index2 = 0;
for (int i = 0; i < res.size(); i++) {
if (compare(nums1, index1, nums2, index2) > 0) res[i] = nums1[index1++];
else res[i] = nums2[index2++];
}
return res;
}
int compare(vector<int>& nums1, int index1, vector<int>& nums2, int index2) {
int m = nums1.size(), n = nums2.size();
while (index1 < m && index2 < n) {
int diff = nums1[index1] - nums2[index2];
if (diff != 0) return diff;
index1++;
index2++;
}
return (m - index1) - (n - index2);
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size(), n = nums2.size();
vector<int> res(k, 0);
int start = max(0, k - n); // k - n <= i
int end = min(k, m); // i <= m
for (int i = start; i <= end; i++) {
vector<int> v1(getKElem(nums1, i)); // i <= m
vector<int> v2(getKElem(nums2, k - i)); // k - i <= n
vector<int> vec(merge(v1, v2));
if (compare(vec, 0, res, 0) > 0) res.swap(vec);
}
return res;
}
