【烧脑算法】最小字典序：巧用单调栈，从栈底到最优解
目录
前言
最小字典序题目
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 st; for(int i=0;inums[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 mostCompetitive(vector& nums, int k) { //就是一个简单的单调栈,遍历数组,栈中元素是单调递增的即可 int n=nums.size(); vector ret; //用数组模拟栈 for(int i=0;inums[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;is[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 arrangeBookshelf(vector& nums, int limit) { int n=nums.size(); unordered_map m; //统计数组中各个数组出现的次数 for(auto e:nums) m[e]++; //使用单调栈 vector ret; unordered_map have; //存储数组中已经存在的数字及个数 for(int i=0;ilimit保证后面的个数和已经存在的个数>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 mostCompetitive(vector& nums, int k) { //就是一个简单的单调栈,遍历数组,栈中元素是单调递减的即可 int n=nums.size(); vector ret; //用数组模拟栈 for(int i=0;i<n;i++) { while(!ret.empty()&&ret.back()k) //(n-i)+ret.size()>k保证栈中的元素+后面的元素>k { ret.pop_back(); } ret.push_back(nums[i]); } ret.resize(k); return ret; }public: vector maxNumber(vector& nums1, vector& nums2, int k) { int n1=nums1.size(),n2=nums2.size(); vector ret; for(int i=0;i<=k&&i<=n1;i++) { if(n1<i) break; if(n2<k-i) continue; vector tmp1=mostCompetitive(nums1,i); vector tmp2=mostCompetitive(nums2,k-i); auto compare=[&](int _p,int _q) //对两个数组从_p和_q位置后开始比较 { while(_p<i&&_qtmp2[_q]; }; vector 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 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;is[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部：
- 保留什么样的数据到栈中；
- 栈是递增还是递减的；
- 栈的长度时候又要求，出栈时有没有其他限制。
对于有些复杂的单调栈题目要对题目分割，分板块处理。
