本文涉及知识点

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^5$
s 只包含小写英文字母。

贪心

性质一：N = s.lenght。 p的长度一定是N。
性质二：如果s中不存在比t.back小的字符，则打印t.back是不劣解。
性质三：如果s中存在比t.back小的字符，则打印t.back一定不是最优解。

代码

核心代码

class Solution {
		public:
			string robotWithString(string s) {
				vector<int> LessIndex(26,-1);//LessIndex[i]表示小于'a'+i的最大坐标，不存在为-1
				for (int i = 0;i < s.length();i++) {
					for (int j = 0;j < 26;j++) {
						if (s[i] < 'a' + j) { LessIndex[j] = i; }
					}
				}
				string str,t;
				for (int i = 0;i < s.length();i++) {
					t += s[i];
					while (t.size() && (LessIndex[t.back() - 'a'] <= i)) { str += t.back();t.pop_back(); }
				}				
				return str + 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);
		}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。