Minimal string

lgydkkyd · 2024-01-02 22:53:11 · 题解

点开题面，输出字典序最小的出栈序列这几个大字很显眼，不用想就知道这提示一道有一点点进阶的贪心，因为这题融合了栈，但是只要用栈写便不成问题了。而根据传统的贪心题的做法，要想写代码必须找到贪心策略，而这题由于让我们找尽量小的字典序无非就是让小的字母尽量排在前面,如果说当前的字符比还没有进栈的所有字母全都要要小，那么这样一来输出当前字符就是字典序最小的方案也就是该样例的最优解。然后就是代码实现的环节，但是乍一看数据绝对值有 10^5 ，很容易会出现超时的情况。这里就需要接触到另外一个概念，预处理。需要提前建一个类型为字符串的 q 数组，用来记录第 i 个元素后面的元素最大哪一个字母。经过这样的优化时间复杂度也就由原来的 O(|s|^2) 成功缩短到了 O(|s|)，自然也就可以通过此题了。

Code

#include<bits/stdc++.h>
using namespace std;
char q[114514],r[114514];//记录第i个元素后面的元素最大是什么的数组和输入的字符串 
stack<char>p;
int main(){
    cin>>r;//输入字符串 
    int rlen=strlen(r);//记录长度 
    q[rlen]='z'+1;//初始化，因为字符一定是小写字母，z+1就避免了重复 
    for(int i=rlen-1;i>=0;i--){//倒序遍历 
        q[i]=min(q[i+1],r[i]);//初始化一下q数组 
    }
    for(int i=0;i<rlen;i++){
        p.push(r[i]);//入栈元素 
        while(!p.empty()){
            if(p.top()>q[i+1])break;//不满足条件可以跳出循环 
            putchar(p.top());//满足则输出，且使栈顶出栈
            p.pop();
        }
    }
    while(!p.empty()){
        putchar(p.top());//输出当前栈顶 
        p.pop();//栈顶出队 
    }
    return 0;//华丽结束``` 
}