title
给你一个字符串 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只包含小写英文字母。
solution
本题是经典贪心：求出栈序列的最小字典序。
我们首先将题目描述进行转化：有一个初始为空的栈，给定字符的入栈顺序，求字典序最小的出栈序列。
class Solution:
def robotWithString(self, s: str) -> str:
stack = []
import collections
counter = collections.Counter(s)
ans = []
'''
栈模拟, 栈顶是最小的就弹出，否则就继续入栈等有更小的弹出
'''
for c in s:
# 判断后面是否还有比它小的
counter[c] -= 1
minc = c
for x in string.ascii_lowercase:
if counter[x] > 0:
minc = x
break
# print(c, minc)
stack.append(c)
while stack and stack[-1] <= minc:
ans.append(stack.pop())
return "".join(ans + stack[::-1])
class Solution:
def robotWithString(self, s: str) -> str:
stack = []
ans = []
minc = [None] * (len(s) + 1)
t = 'z'
for i in range(len(s) - 1, -1, -1):
t = min(t, s[i])
minc[i] = t
minc[-1] = chr(ord('z') + 1)
'''
栈模拟, 栈顶是最小的就弹出，否则就继续入栈等有更小的弹出
'''
for i, c in enumerate(s):
# 判断后面是否还有比它小的
stack.append(c)
while stack and stack[-1] <= minc[i + 1]:
ans.append(stack.pop())
return "".join(ans + stack)
if __name__ == '__main__':
f = Solution().robotWithString
print("actual:", f("caba"), "should:", None)
print("actual:", f("bac"), "should:", None)
print("actual:", f("bdda"), "should:", None)