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 <= 105
s 只包含小写英文字母。

解法：贪心

本题是经典贪心：求出栈序列的最小字典序。

我们首先将题目描述进行转化：有一个初始为空的栈，给定字符的入栈顺序，求字典序最小的出栈序列。

当一个字符入栈后，我们持续检查栈顶元素 c。设还未入栈的字符中，字典序最小的字符是 m，有以下两种情况。

c \le m：此时弹出 c 最优。如果此时按兵不动，下一个出栈的将会是大等于 c 的字符，答案不会变优。
c > m：此时不弹出 c，等待后续更小的字符入栈。

所有字符都入栈后，栈内的剩余字符按顺序弹出即可。复杂度 \mathcal{O}(n)。

参考代码（c++）

class Solution {
public:
    string robotWithString(string s) {
        int n = s.size();
        vector<char> f(n + 1);
        f[n] = 'z' + 1;
        for (int i = n - 1; i >= 0; i--) f[i] = min(f[i + 1], s[i]);

        string ans;
        stack<char> stk;
        for (int i = 0; i < n; i++) {
            stk.push(s[i]);
            while (!stk.empty() && stk.top() <= f[i + 1]) ans.push_back(stk.top()), stk.pop();
        }
        return ans;
    }
};