class Solution {
public:
string robotWithString(string s) {
}
};
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 <= 105s 只包含小写英文字母。原站题解
golang 解法, 执行用时: 32 ms, 内存消耗: 6.8 MB, 提交时间: 2022-11-18 14:35:10
func robotWithString(s string) string {
ans := make([]byte, 0, len(s))
cnt := [26]int{}
for _, b := range s {
cnt[b-'a']++
}
min := byte(0) // 剩余最小字母
st := []byte{}
for _, c := range s {
cnt[c-'a']--
for min < 25 && cnt[min] == 0 { // 找到第一个正数
min++
}
st = append(st, byte(c))
for len(st) > 0 && st[len(st)-1]-'a' <= min {
ans = append(ans, st[len(st)-1])
st = st[:len(st)-1]
}
}
return string(ans)
}
python3 解法, 执行用时: 840 ms, 内存消耗: 17.8 MB, 提交时间: 2022-11-18 14:34:53
'''
提示 1
t 是一个栈。
问题相当于从左到右遍历 s，在允许用一个辅助栈的前提下，计算能得到的字典序最小的字符串。
提示 2
贪心地思考，为了让字典序最小，在遍历 s 的过程中，如果栈顶字符 ≤ 后续字符（未入栈）的最小值，
那么应该出栈并加到答案末尾，否则应当继续遍历，取到比栈顶字符小的那个字符，这样才能保证字典序最小。
提示 3
代码实现时，为了快速判断剩余字符的最小值，我们可以先统计 s 每个字符的出现次数 cnt，
然后在遍历 s 的过程中更新 cnt，这样 cnt 中第一个正数对应的字符就是剩余字符中最小的。
'''
class Solution:
def robotWithString(self, s: str) -> str:
ans = []
cnt = Counter(s)
_min = 0 # 剩余最小字母
st = []
for c in s:
cnt[c] -= 1
while _min < 25 and cnt[ascii_lowercase[_min]] == 0:
_min += 1
st.append(c)
while st and st[-1] <= ascii_lowercase[_min]:
ans.append(st.pop())
return ''.join(ans)