目录
前言
最小字典序类型的题目是算法题中比较有难度的一部分，在大厂面试时出现频率也不算低，所以研究这类题目也是有必要的。最小字典序类题目思路通常以单调栈作为突破口，如果你单调栈类型题目写的游刃有余，那么关于字典序这类题目必定也会一点就通，以下结合具体题目来剖析。
PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。
最小字典序题目
402. 移掉 K 位数字
删除k个字符使得重新组成的数字最小；思考在什么情况下会进行元删除？？？
- 毫无疑问，一定是从前往后进行删除，因为前面是高位，高位改变对数字的影响更大；
- 从前往后如何进行删除呢？？？删除k个数字，不论如何删除最后的数字位数一定是n-k个，数字位数是一定的，那么尽可能的让高位数字更小；
- 从前往后遍历，将相邻的数字进行比较，如果后面的数字更小，就将前面的数字删除，让后面的数字补位会从而实现高位数字更小。
class Solution {
public:
string removeKdigits(string nums, int k) {
//单调栈维护前面的数字
int n=nums.size();
vector<char> st;
for(int i=0;i<n;i++)
{
while(!st.empty()&&st.back()>nums[i]&&k) //对前一个数字进行删除
{
st.pop_back();
k--;
}
st.push_back(nums[i]); //将当前数字加入
}
while(k&&!st.empty()) //如果k没有用完,从后往前删除
{
st.pop_back();
k--;
}
string ret;
int i=0,len=st.size();
while(i<len&&st[i]=='0') i++; //处理前导0
while(i<len)
ret+=st[i++];
return ret==""?"0":ret;
}
};1673. 找出最具竞争力的子序列
一个简单的单调栈，此题直接维护一个递增的单调栈遍历所有元素即可，不过要保证栈中的元素有k个。
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
//就是一个简单的单调栈,遍历数组,栈中元素是单调递增的即可
int n=nums.size();
vector<int> ret; //用数组模拟栈
for(int i=0;i<n;i++)
{
while(!ret.empty()&&ret.back()>nums[i]&&(n-i)+ret.size()>k) //(n-i)+ret.size()>k保证栈中的元素+后面的元素>k
{
ret.pop_back();
}
ret.push_back(nums[i]);
}
ret.resize(k);
return ret;
}
};316. 去除重复字母
先根据示例二模拟一遍：
1. 下标0位置："c"入，此时字符串"c";
2. 下标1位置："b"<"c"，如果b在前面字典序更小并且后面还有"c"，让前面的"c"出，此时字符串"b";
3. 下标2位置，"a"<"b"，前面"b"出了，后面还有b，"字符串a"；
4. 下标3位置，"c">"a"，入"ac"；
5. 下标4位置，"d">"c"，入"acd"；
6. 下标5位置，"c"，前面有c了不用入了；
7. 下标6位置，"b"<"d"，d不能出因为后面没有d了，入b，"acdb"；
8. 下标7位置，"c"有c了不用入。
综上所述，最后的结果已经出来了就是"acdb"，所以依旧是使用单调栈让字符单调递增，但是如果字符已经使用完了就不能在出栈了。
class Solution {
public:
string removeDuplicateLetters(string s) {
int n=s.size();
int ch[26]={0}; //存储每个字符出现的次数
for(auto e:s) ch[e-'a']++;
string ret; //用string模拟栈
int have[26]={0};
for(int i=0;i<n;i++)
{
if(have[s[i]-'a']) //ret中已经存在该字符了
{
ch[s[i]-'a']--;
continue;
}
while(!ret.empty()&&ret.back()>s[i]&&ch[ret.back()-'a']) //将前面字符删除
{
have[ret.back()-'a']--;
ret.pop_back();
}
ret.push_back(s[i]); //将该字符加入
have[s[i]-'a']++;
ch[s[i]-'a']--;
}
return ret;
}
};Q3. 整理书架
单调栈，此题需要添加一个条件就是limit，对于一个数字来说，如果ret中存在的个数+后面还有的个数>limit时才能将该数字出栈。
class Solution {
public:
vector<int> arrangeBookshelf(vector<int>& nums, int limit) {
int n=nums.size();
unordered_map<int,int> m; //统计数组中各个数组出现的次数
for(auto e:nums) m[e]++;
//使用单调栈
vector<int> ret;
unordered_map<int,int> have; //存储数组中已经存在的数字及个数
for(int i=0;i<n;i++)
{
if(have.count(nums[i])&&have[nums[i]]==limit)
{
m[nums[i]]--;
continue;
} //have[ret.back()]+m[ret.back()]>limit保证后面的个数和已经存在的个数>limit才能出
while(!ret.empty()&&ret.back()>nums[i]&&m[ret.back()]&&have[ret.back()]+m[ret.back()]>limit)
{
have[ret.back()]--;
ret.pop_back();
}
have[nums[i]]++;
ret.push_back(nums[i]);
m[nums[i]]--;
}
return ret;
}
};321. 拼接最大数
此题类似于1673题，是哪一题的变形。
有两个数组，要对数组进行整合，找到最大数。
毫无疑问根据经验要使用单调栈，但是两个数组要如何同时处理？？？
当两个数组依次处理不好搞时，能不能一个个的搞；假设nums1中取0,1,2,3,4,....k个,那么nums2中取出多少个就是固定的了，这样就可以一个个的处理 。
将两个数组的最大数在进行整合，就可以得到长度为k的最大数；
细节：在进行整合的时候要找两个数组不相同的位置进行比较。比如[4,3,8]和[4,9]，在进行整合的时候不能用第一个4进行比较，而是使用3和9进行比较。
class Solution {
vector<int> mostCompetitive(vector<int>& nums, int k) {
//就是一个简单的单调栈,遍历数组,栈中元素是单调递减的即可
int n=nums.size();
vector<int> ret; //用数组模拟栈
for(int i=0;i<n;i++)
{
while(!ret.empty()&&ret.back()<nums[i]&&(n-i)+ret.size()>k) //(n-i)+ret.size()>k保证栈中的元素+后面的元素>k
{
ret.pop_back();
}
ret.push_back(nums[i]);
}
ret.resize(k);
return ret;
}
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n1=nums1.size(),n2=nums2.size();
vector<int> ret;
for(int i=0;i<=k&&i<=n1;i++)
{
if(n1<i) break;
if(n2<k-i) continue;
vector<int> tmp1=mostCompetitive(nums1,i);
vector<int> tmp2=mostCompetitive(nums2,k-i);
auto compare=[&](int _p,int _q) //对两个数组从_p和_q位置后开始比较
{
while(_p<i&&_q<k-i&&tmp1[_p]==tmp2[_q]) _p++,_q++; //找不同的位置
if(_p==i) return false;
if(_q==k-i) return true;
return tmp1[_p]>tmp2[_q];
};
vector<int> each;
int p = 0, q = 0;
while (p < i && q < k - i)
{
if (compare(p,q)) each.push_back(tmp1[p++]);
else each.push_back(tmp2[q++]);
}
while (p < tmp1.size()) each.push_back(tmp1[p++]);
while (q < tmp2.size()) each.push_back(tmp2[q++]);
if(each>ret) ret=each;
}
return ret;
}
};2030. 含特定字母的最小子序列
如果此题没有要求leeter以及repetition，那么此题就于上面的第1673题很显示。
所以此题可以对上面一题的代码进行修改，加一层判断，后面的letter字符够不够，以及repetition的次数够不够。
class Solution {
public:
string smallestSubsequence(string s, int k, char letter, int repetition) {
//就是一个简单的单调栈,遍历数组,栈中元素是单调递增的即可
int n=s.size(),all=0;
for(auto e:s)
if(e==letter) all++;
string ret; //用数组模拟栈
int have=0;
for(int i=0;i<n;i++)
{
while(!ret.empty()&&ret.back()>s[i]&&(n-i)+ret.size()>k) //(n-i)+ret.size()>k保证栈中的元素+后面的元素>k
{
if(ret.back()==letter&&have+all==repetition) break;
if(ret.back()==letter) have--;
ret.pop_back();
}
//判断ret剩余的位置够不够放其他字符
if(s[i]==letter) have++,all--;
if(k-ret.size()==repetition-have&&s[i]!=letter) continue;
//k-ret.size()表示字符串还差的字符,repetition-have表示还差的letter字符,如果两者相等说明后面要全放letter字符
ret.push_back(s[i]);
}
ret.resize(k);
return ret;
}
};总结
对上面的题目进行分析，不难看出最小字典序类型解题就分3部：
- 保留什么样的数据到栈中；
- 栈是递增还是递减的；
- 栈的长度时候又要求，出栈时有没有其他限制。
对于有些复杂的单调栈题目要对题目分割，分板块处理。