leetcode 2434. 使用机器人打印字典序最小的字符串 中等

给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

• 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
• 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。

请你返回纸上能写出的字典序最小的字符串。

示例 1：

输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="zza" ，t="" 。
执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。

示例 2：

输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
执行第二个操作，得到 p="abc" ，s="" ，t="" 。

示例 3：

输入：s = "bdda"
输出："addb"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="bdda" ，t="" 。
执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。

提示：

• 1 <= s.length <= 10^5
• s 只包含小写英文字母。

分析：题目实际上给出了一个入栈序列，要求出栈序列的字典序最小。可以先将入栈序列的所有字符出现次数记录到一个长度为 26 的数组中，并记录最小出现的字符序号 pos。之后遍历字符串 s，如果当前的字符序号是 pos，则直接加入答案序列 ans 的末尾；否则将这个字符放到字符串 t 中。每次寻找一个字符，都要把对应位置的出现次数减 1。当 pos 的字符全部出现后，找到下一个 pos 的位置，并对字符串 t 从后向前检查是否出现了新的 pos 字符，直到不是为止。这样遍历完字符串 s，再把 t 拼接到 ans 上即可。

char* robotWithString(char* s) {
    char *ans=(char*)malloc(sizeof(char)*100010);memset(ans,0,sizeof(ans));
    char t[100010];
    int s_len=strlen(s),t_len=0,pos=30,len=0;
    int flag[30]={0};
    for(int i=0;i<s_len;++i)
        flag[s[i]-'a']++,pos=fmin(pos,s[i]-'a');
    for(int i=0;s[i];++i)
    {
        if(s[i]-'a'==pos)ans[len++]=s[i],flag[pos]--;
        else if(flag[pos])t[t_len++]=s[i],flag[s[i]-'a']--;
        else
        {
            for(int j=pos+1;j<26;++j)
            {
                if(flag[j])
                {
                    pos=j;break;
                }
            }
            while(t_len&&t[t_len-1]-'a'<=pos)
                ans[len++]=t[t_len-1],t_len--;
            i--;
        }
    }

    while(t_len)
        ans[len++]=t[t_len-1],t_len--;
    ans[len]=0;
    return ans;
}