目标
给你一个字符串 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^5
- s 只包含小写英文字母。
思路
- 首先统计字符串中的字符个数，要使输出的字典序最小，那么第一个字符一定是字符串中出现过的字典序最小的字符
- 为了将该字符打印到首位，需要先定位到这个字符，它前面的字符都会被暂存到栈中
- 确定了第一个字典序最小的字符之后，下一个字符有两个选择，取栈顶字符，或者找到剩下的字符中的字典序最小的
需要维护剩余字符中最小字典序的字符，可以使用有序集合或者后缀。
代码
/**
* @date 2025-06-06 8:47
*/
public class RobotWithString2434 {
public String robotWithString(String s) {
TreeMap<Character, Integer> map = new TreeMap<>();
char[] chars = s.toCharArray();
int n = chars.length;
for (char c : chars) {
map.merge(c, 1, Integer::sum);
}
ArrayDeque<Character> q = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < n) {
Character min = map.firstKey();
while (i < n && chars[i] != min) {
char c = chars[i++];
q.offer(c);
map.merge(c, -1, Integer::sum);
if (map.get(c) == 0) {
map.remove(c);
}
}
sb.append(min);
map.merge(min, -1, Integer::sum);
if (map.get(min) == 0) {
map.remove(min);
}
i++;
while (!q.isEmpty() && (map.size() == 0 || q.peekLast() <= map.firstKey())) {
sb.append(q.pollLast());
}
}
return sb.toString();
}
}
性能
