栈+贪婪，LeetCode 2434. 使用机器人打印字典序最小的字符串
一、题目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_lowercasefrom collections import Counterclass Solution:
def robotWithString(self, s: str) -> str: n = len(s) mi = 0 res = [] cnt = Counter(s) st = [] for x in s: cnt -= 1 while mi < 25 and cnt] == 0: mi += 1 st.append(x) while st and st[-1] <= ascii_lowercase: res.append(st.pop()) return ''.join(res)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]