当前位置：首页 > web >正文

LeetCode 2434.使用机器人打印字典序最小的字符串：贪心(栈)——清晰题解

web 2025/6/27 12:25:58

【LetMeFly】2434.使用机器人打印字典序最小的字符串：贪心(栈)——清晰题解

力扣题目链接：https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/

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

解题方法：贪心

机器人的操作等价于：

将字符串s中的元素按顺序入栈，栈中元素按任意顺序出栈，最终所有元素都要入栈出栈，求出栈元素组成的字符串的最小字典序。

分析这道题最好的例子就是bac：

首先b入栈，这时候b应该出栈吗？不应该，因为后面有更小的a，应该让a排前面；

接着将a入栈，此时栈中元素为[ba，a应该出栈吗？应该，因为后面元素都比a大，一旦c入栈时a还没出栈，那么c一定比a出栈早；

a出栈后b应该出栈吗？应该，和a出栈的道理相同，因为b < c；

c入栈，c出栈，最终顺序abc。

不知道大家有没有发现，决定一个元素是否出栈的依据是后面最小的元素是否都大于等于栈顶元素 。

如果后面元素都大于等于栈顶元素，那么栈顶元素是时候出栈了，否则后面更大的元素入栈只会导致有更大的元素先出栈；
如果后面元素有比栈顶元素更小的，那么栈顶元素就先不出栈，因为更小元素更早出栈结果更优。

具体的：

预先后续遍历一遍字符串s，求出mini数组，其中mini[i]代表s[i:n-1]的最小字符。

接着正序遍历字符串s，遍历到谁谁入栈，当栈顶元素小于等于字符串当前位置之后的所有字符时，栈顶元素不断出栈。

为了方便，也可以假设原始字符串s后面还有一个“最大”字符z。

时间复杂度 $O (l e n (s))$
空间复杂度 $O (l e n (s))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-06-06 21:49:43* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-06 22:19:18*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endifclass Solution {
public:string robotWithString(string s) {vector<char> mini(s.size() + 1, 'z');for (int i = s.size() - 1; i >= 0; i--) {mini[i] = min(mini[i + 1], s[i]);}stack<char> st;string ans;for (int i = 0; i < s.size(); i++) {st.push(s[i]);while (st.size() && st.top() <= mini[i + 1]) {ans += st.top();st.pop();}}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-06-06 21:49:43
LastEditors: LetMeFly.xyz
LastEditTime: 2025-06-06 22:30:06
'''
class Solution:def robotWithString(self, s: str) -> str:mini = ['z'] * (len(s) + 1)for i in range(len(s) - 1, -1, -1):mini[i] = min(mini[i + 1], s[i])ans = []st = []for i, c in enumerate(s):st.append(c)while st and st[-1] <= mini[i + 1]:ans.append(st.pop())return ''.join(ans)

Java

/** @Author: LetMeFly* @Date: 2025-06-06 21:49:43* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-06 22:38:18*/
// StringBuilder - java.lang
import java.util.Deque;
import java.util.ArrayDeque;class Solution {public String robotWithString(String s) {char[] mini = new char[s.length() + 1];mini[s.length()] = 'z';for (int i = s.length() - 1; i >= 0; i--) {mini[i] = (char) Math.min(mini[i + 1], s.charAt(i));}StringBuilder ans = new StringBuilder(s.length());Deque<Character> st = new ArrayDeque<>();for (int i = 0; i < s.length(); i++) {st.push(s.charAt(i));while (!st.isEmpty() && st.peek() <= mini[i + 1]) {ans.append(st.pop());}}return ans.toString();}
}

Go

/** @Author: LetMeFly* @Date: 2025-06-06 21:49:43* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-06 23:06:01*/
package mainfunc robotWithString(s string) string {mini := make([]byte, len(s) + 1)mini[len(s)] = 'z'for i := len(s) - 1; i >= 0; i-- {mini[i] = min(mini[i + 1], s[i])}st := mini[:0]ans := make([]byte, 0, len(s))for i := 0; i < len(s); i++ {st = append(st, s[i])for len(st) > 0 && st[len(st) - 1] <= mini[i + 1] {ans = append(ans, st[len(st) - 1])st = st[:len(st) - 1]}}return string(ans)
}