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

【C++栈】2434. 使用机器人打印字典序最小的字符串|1953

news 2025/7/15 12:27:53

本文涉及知识点

C++栈

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

给你一个字符串 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的最小字符是ch，假定有c个，则将所有的ch放到t后，马上写到张上。即c个ch开头。
令除ch外，最小的字符是ch1。
如果t的尾部是ch1，则将t尾部的ch1写到纸上，将所有的ch1放到t后，马上写到纸上。
$\vdots$
以ch开头，ch尽可能的多。
ch后面紧跟着ch1，如果ch的数量相等，ch1尽可能的多。
$\vdots$
s中的ch(ch1等)一定能全部写到纸，t中只有尾部能放。 t的尾部如果<= ch，则全部放。
end[ch] 记录值为ch的最大下标。

如果存在s[i] > s[j] 且i < j。则s[i]必须等s[j]
t.back()如果大于任意未处理s[j]，也必须等待。

代码

核心代码

class Solution {public:string robotWithString(string s) {vector<int> end(26, -1);for (int i = 0; i < s.length(); i++) {end[s[i] - 'a'] = i;}string t, ret;for (int i = 0,cur=0; i < s.length(); i++) {while(true) {while (t.size() && ('a' + cur >= t.back())) {ret += t.back();t.pop_back();}if (end[cur] >= i) { break; }cur++;						}					if (s[i] == 'a' + cur ) {ret += s[i];			}else {t += s[i];}}return ret + string(t.rbegin(), t.rend());}};

核心代码

class Solution {public:string robotWithString(string s) {vector<int> end(26, -1);for (int i = 0; i < s.length(); i++) {end[s[i] - 'a'] = i;}string t, ret;for (int i = 0,cur=0; i < s.length(); i++) {while (end[cur] < i) {cur++;}while (t.size() && ('a' + cur >= t.back())) {ret += t.back();t.pop_back();}if (s[i] == 'a' + cur ) {ret += s[i];			}else {t += s[i];}}return ret + string(t.rbegin(), t.rend());}};

单元测试

string s;TEST_METHOD(TestMethod11){s = "zza";auto res = Solution().robotWithString(s);AssertEx(string("azz"), res);}TEST_METHOD(TestMethod12){s = "bac";auto res = Solution().robotWithString(s);AssertEx(string("abc"), res);}TEST_METHOD(TestMethod13){s = "bdda";auto res = Solution().robotWithString(s);AssertEx(string("addb"), res);}TEST_METHOD(TestMethod14){s = "vzhofnpo";auto res = Solution().robotWithString(s);AssertEx(string("fnohopzv"), res);}TEST_METHOD(TestMethod15){s = "mmuqezwmomeplrtskz";auto res = Solution().robotWithString(s);AssertEx(string("eekstrlpmomwzqummz"), res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功