给一个长度为n的字符串，找出长度为m的最小字典子序列【单调栈】

一个大大的分割线，如果这个傻逼题没有被成为某某复赛的签到题，可能我一会都经常傻逼下去了。

【2019计蒜之道复赛——星云系统】

题目是，给出一个长度为n(1<n<5e6)的只有大写字母的字符串，然后找出一个长度为m的最小字典子序列。

更新： 这是一道简单得要死掉的单调栈裸题，为什么没想到呢栈字母表，因为想法是，利用单调栈尽量求取结果字符串的最优值，也就说结果字符串在理想状况下是递增的，但是非理想状况是什么呢？因为有需要限定k个字母存在，因此被删掉的字母数量为len-k个字符，当被单调栈弹出的字节数量超过n-k个时，剩余的字符【即单调栈中的递减字符或者未遍历到的剩余字符】就组成了最小字典序ans。

散了散了。。。时间复杂度是线性扫描的O(n)

想想也有，题面都这个数量级了，还要啥常数。线性就完了。

#include<bits/stdc++.h>
#define M(a,b) memset(a,b,sizeof a)
#define LL long long
using namespace std;
const int maxn=5000007;
char a[maxn];
stack<char>q;
int n,m;
int main()
{
    while(!q.empty())q.pop();
    scanf("%s %d",a,&m);
    n=strlen(a);
    int cnt=0;
    int flag=n;
    for(int i=0; i<n; i++)
    {
        if(q.empty())q.push(a[i]);
        else
        {
            if(a[i]>q.top())q.push(a[i]);
            else
            {
                while(!q.empty()&&q.top()>a[i])
                {
                    q.pop();
                    cnt++;
                    if(cnt>=n-m)
                    {
                        flag=i;
                        break;
                    }
                }
                q.push(a[i]);
            }
        }
        if(cnt>=n-m)break;
    }
    string ans="";
    for(int i=n-1;i>flag;i--)ans+=a[i];
    while(!q.empty())ans+=q.top(),q.pop();
    reverse(ans.begin(),ans.end());
    ans=ans.substr(0,m);
    cout<<ans<<"\n";
}

头条一面挂了，除了自己菜，数据结构和基础常识理解不够深刻外，还有就是面试时激动得屁股疼到抽筋。。。可能是绝症了

言归正传，面试官本来想随意出个签到题玩一下开个场，结果被我紧张的崩了。

结束面试时候理智出来仔细想了下并不难

题目是，给出一个长度为n(1<n<10000)的只有大写字母的字符串，然后找出一个长度为m的最小字典子序列。

如 orange

当m=3时，输出结果age

若borange,且长度为3时，同样输出age

面试的时侯脑子一团浆糊，想到了标号和顺序，直接被举例否定了。

如果用最暴力的观念，找到n个字节里字典序最小且位序小于等于m的字母，然后砍去这个字母之前的字母，在剩余的字母中又找一个字典序最小的字母，这样常常找m个就好了。

唯一要考量的条件就是，这样不断贪心取最小的规定是，要确保取了某个字母后，剩余待选串中的字符个数要小于等于m。

于是想到一个 复杂度为O(n*m) 的做法，每次递归n字符串，查找符合条件的字符，再从头扫一遍找下一个字符。从头扫的缘由是，当找到了一个字符，比如b，无法判定是否里面的字符是否存在一个字典序小于b的数组，所以仍要递归完整个串就能得到一个最小值。这样是不可取的，必须进行优化。

那么做一个预处理，首先26个vector内存每个字母出现位置的数组，O(n)遍历字符串，push进每个字母出现数组，因为是排序遍历栈字母表，所以每位vector都是有序的。

然后遍历m次这26个vector，找出第一个字母的出现位置，满足<=n-(m-i)+1,说明存在一个较小的字母符合筛选条件，并且不用关心该位置剩余字符串是否存在比其更小的字母，如果存在，在字典序遍历其他vector就需要找到了。在ans中填入这个字母，然后从a字母开始再次查找下标大于上一个填入ans中字母下标的符合条件的字母。这个在有序vector中查找位置直接用二分即可。

最后时间复杂度O(26*m),空间复杂度O(n)

代码如下：

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-127244-1.html