使用机器人打印字典序最小的字符串

难度: Medium

给你一个字符串 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 <= 10⁵
s 只包含小写英文字母。

Submission

运行时间: 82 ms

内存: 18.5 MB

class Solution:
    def robotWithString(self, s: str) -> str:
        ans = []
        stk = []

        while s:
            mn = min(s)
            while stk and stk[-1] <= mn:
                ans.append(stk.pop())
            i = s.rindex(mn)
            ans.append(mn * s.count(mn))
            stk.extend(s[:i + 1].replace(mn, ''))
            s = s[i + 1:]
        
        return ''.join(chain(ans, reversed(stk)))

Explain

此题解的基本思路是使用两个辅助容器：一个动态数组 `ans` 用于存储最终结果，一个栈 `stk` 用于临时存储字符。算法从头到尾遍历字符串 `s`，每次找出 `s` 中剩余部分的最小字符，并将其加入到结果字符串 `ans` 中。若栈顶字符小于等于 `s` 中的最小字符，则将栈顶字符弹出并加入到 `ans`。接着，将 `s` 中最小字符之前的所有字符（不包括最小字符本身）加入到栈中。这样做可以保证栈 `stk` 中的字符始终保持相对有序，从而在每次从 `s` 中提取最小字符后，可以有效地将栈中较小的字符移入 `ans`。最后，将 `stk` 中剩余的字符逆序后加入到 `ans` 中，以保证字典序最小。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def robotWithString(self, s: str) -> str:
        ans = []  # 存储最终结果的数组
        stk = []  # 临时存储字符的栈

        while s:  # 遍历字符串 s 直到为空
            mn = min(s)  # 找到 s 中的最小字符
            while stk and stk[-1] <= mn:  # 将栈中所有小于等于最小字符的元素弹出并加入结果
                ans.append(stk.pop())
            i = s.rindex(mn)  # 找到最小字符在 s 中的最后一个索引
            ans.append(mn * s.count(mn))  # 将最小字符按其在 s 中的数量加入结果
            stk.extend(s[:i + 1].replace(mn, ''))  # 将最小字符之前的所有字符加入栈中
            s = s[i + 1:]  # 更新 s 为最小字符之后的子串
        
        return ''.join(chain(ans, reversed(stk)))  # 将结果列表和栈中剩余字符合并并转换为字符串

Explore

在算法中选择将栈中小于等于最小字符的元素弹出并加入结果的做法，主要是为了保证结果字符串的字典序最小。栈用于暂存字符，并可以通过控制字符的入栈和出栈顺序来确保最终结果的有序性。当栈顶的字符小于等于字符串s中未处理部分的最小字符时，意味着栈顶的字符在字典序上不可能被后来的任何字符替代为更小，因此可以安全地将其加入到结果字符串中，从而确保整体上的字典序最小化。

虽然使用`min(s)`和`s.rindex(mn)`可以直接定位到最小字符及其最后一个索引，这种方法简单直观，但每次循环调用这些操作会导致时间复杂度较高，特别是对于长字符串效率不是最优。一种更高效的方法是使用优先队列（或称为最小堆）来跟踪未处理字符串中的每个字符及其索引，这样可以在对数时间内找到当前最小的字符和它的索引，从而提高整体算法的效率。

使用`s[:i + 1].replace(mn, '')`确实可能影响算法的效率，因为这种方法在每次循环中都会进行一次字符串切片操作和一次字符替换操作，这两者都是线性时间复杂度的操作。一个优化方法是在一开始就使用一个计数数组来记录每个字符的出现次数，然后根据需要更新计数并直接从计数数组中决定哪些字符应该入栈，避免了不必要的字符串操作，从而提高效率。

在栈和字符串`s`都有字符的情况下，决策依据是栈顶元素与`s`中剩余部分的最小字符的比较。如果栈顶元素小于或等于`s`中的最小字符，那么应该从栈中弹出字符并将其加入到结果字符串中，因为这样可以保持结果的字典序最小。如果栈顶元素大于`s`中的最小字符，那么应该继续处理字符串`s`，将新的字符按逻辑加入栈中，直到可以安全地移动栈顶元素到结果中。