栈+贪婪，LeetCode 2434. 使用机器人打印字典序最小的字符串 ...

一、题目

1、题目形貌

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

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

  请你返回纸上能写出的字典序最小的字符串。
  2、接口形貌

python3

1.  ​

复制代码

1. class Solution:
2.     def robotWithString(self, s: str) -> str:

复制代码

1. [/code]
2. [size=3]3、原题链接[/size]
4. 2434. 使用机器人打印字典序最小的字符串
5. [hr]
6. [size=4]二、解题报告[/size]
8. [size=3]1、思绪分析[/size]
10. 可见 字符串 t 就是一个栈，我们可以考虑在恣意时刻让栈顶出栈
11. 为了得到字典序最小结果，我们何时不得不出栈呢？
12. 当栈顶不大于剩余字符的最小值时，我们不得不出栈
13. 那么维护栈，并模拟即可
14. [size=3]2、复杂度[/size]
16.    时间复杂度： O(N)空间复杂度：O(N)
17.   
18. [size=3]3、代码详解[/size]
20. [size=2]python3[/size]
22. [code] ​

复制代码

1. from string import ascii_lowercasefrom collections import Counterclass Solution:
2.     def robotWithString(self, s: str) -> str:        n = len(s)        mi = 0        res = []        cnt = Counter(s)        st = []        for x in s:            cnt[x] -= 1            while mi < 25 and cnt[ascii_lowercase[mi]] == 0:                mi += 1            st.append(x)            while st and st[-1] <= ascii_lowercase[mi]:                res.append(st.pop())        return ''.join(res)

复制代码

1.  ​

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。