[LeetCode] 每日一题 2434. 使用机器人打印字典序最小的字符串（贪心算法 + 栈）
题目描述
给你一个字符串 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="" 。提示
1 <= s.length <= 10^5s只包含小写英文字母。
解题思路
今天这题挺有意思的，刚读完题就察觉出这是个模拟栈操作的题目。题目描述的是将字符串 s 逐个字符交给机器人，机器人把字符推入一个字符串 t 的尾部；接着机器人可以把 t 的最后一个字符写到纸上——这个“写”操作本质上就是栈的弹出操作。
目标是：使最终写在纸上的字符串字典序最小。
如何才能做到这一点？我意识到关键点在于：我们不能随便弹栈，而要在恰当的时候把最优字符写出来。比如当前栈顶字符如果已经是未来（s剩下部分）最小的字符或更小，那么我们就可以放心地将其写出。
为此，我用了一个贪心策略：
从后往前预处理数组
min[i]，表示s[i:]中的最小字符每次将
s[i]压入栈中如果当前栈顶字符比接下来还未处理的最小字符小（或相等），那么就可以弹出它写到纸上
这种策略其实有点像单调栈 + 贪心的组合思路，在保留最优字符的同时尽可能提前输出。
代码实现
class Solution {
public String robotWithString(String s) {
int n = s.length();
if (n <= 1) {
return s;
}
int[] min = new int[n];
min[n - 1] = s.charAt(n - 1);
for (int i = n - 2; i >= 0; i--) {
min[i] = Math.min(min[i + 1], s.charAt(i));
}
int index = 0;
Stack<Character> stack = new Stack<>();
StringBuilder ans = new StringBuilder();
while (index < n) {
stack.push(s.charAt(index));
index++;
while (!stack.isEmpty() && (index >= n || stack.peek() <= min[index])) {
ans.append(stack.pop());
}
}
return ans.toString();
}
}复杂度分析
时间复杂度：
O(n) ⚡，遍历一遍字符串构造最小字符数组，另一遍处理栈操作，总体线性
空间复杂度：
O(n) 🧠，用于栈和最小值数组的额外空间
总结
这道题虽然描述不复杂，但想写出最优解还是得靠一点思维的“触感” 👀一开始我就想到是栈的模拟，但要做对就要结合贪心策略和提前预处理最小值的技巧。写完之后感觉代码思路非常清晰，这种“栈 + 贪心”的组合思维真的很值得多练几道🥰
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。