一、题目
1、题目描述
给你一个字符串
s和一个机器人，机器人当前有一个空字符串t。执行以下操作之一，直到s和t都变成空字符串：
- 删除字符串
s的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到t的尾部。- 删除字符串
t的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。请你返回纸上能写出的字典序最小的字符串。
2、接口描述
python3
class Solution:def robotWithString(self, s: str) -> str:3、原题链接
2434. 使用机器人打印字典序最小的字符串
二、解题报告
1、思路分析
可见 字符串 t 就是一个栈，我们可以考虑在任意时刻让栈顶出栈
为了得到字典序最小结果，我们何时不得不出栈呢？
当栈顶不大于剩余字符的最小值时，我们不得不出栈
那么维护栈，并模拟即可
2、复杂度
时间复杂度： O(N)空间复杂度：O(N)
3、代码详解
python3
from string import ascii_lowercase
from collections import Counterclass Solution:def robotWithString(self, s: str) -> str:n = len(s)mi = 0res = []cnt = Counter(s)st = []for x in s:cnt[x] -= 1while mi < 25 and cnt[ascii_lowercase[mi]] == 0:mi += 1st.append(x)while st and st[-1] <= ascii_lowercase[mi]:res.append(st.pop())return ''.join(res)
