当前位置：首页 > news >正文

【烧脑算法】最小字典序：巧用单调栈，从栈底到最优解

news 2025/7/5 10:46:08

前言

最小字典序题目

402. 移掉 K 位数字

1673. 找出最具竞争力的子序列

316. 去除重复字母

Q3. 整理书架

321. 拼接最大数

2030. 含特定字母的最小子序列

总结

前言

最小字典序类型的题目是算法题中比较有难度的一部分，在大厂面试时出现频率也不算低，所以研究这类题目也是有必要的。最小字典序类题目思路通常以单调栈作为突破口，如果你单调栈类型题目写的游刃有余，那么关于字典序这类题目必定也会一点就通，以下结合具体题目来剖析。

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++;  //处理前导0while(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;}
};