本文涉及知道点

C++栈 模拟
C++贪心

LeetCode3170. 删除星号以后字典序最小的字符串

给你一个字符串 s 。它可能包含任意数量的 ‘’ 字符。你的任务是删除所有的 '’ 字符。
当字符串还存在至少一个 ‘’ 字符时，你可以执行以下操作：
删除最左边的 '’ 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
请你返回删除所有 '’ 字符以后，剩余字符连接而成的
字典序最小 的字符串。
示例 1：
输入：s = "aaba"
输出：“aab”
解释：
删除 ‘’ 号和它左边的其中一个 ‘a’ 字符。如果我们选择删除 s[3] ，s 字典序最小。
示例 2：
输入：s = “abc”
输出：“abc”
解释：
字符串中没有 '’ 字符。
提示：
1 <= s.length <= 10⁵
s 只含有小写英文字母和 ‘’ 字符。
输入保证操作可以删除所有的 '’ 字符。

栈

贪心（决策包容性）：显然有多个最小序字符时，删除最后一个。
indexs[j]记录 s[0…i-1]中为’a’+j的下标，升序。
如果s[i]是’'，则选择j1最大且indexs[j1]非空， s[indexs[j1]]= '’ indexs[j1].pop()。
否则, indexs[s[j]-‘a’].push(i)。
删除s所有的’*'，并返回s。

代码

核心代码

class Solution {
		public:
			string clearStars(string s) {
				stack<int> indexs[26];
				auto Del = [&]() {
					for (int i = 0; i < 26; i++) {
						if (indexs[i].size()) {
							s[indexs[i].top()] = '*';
							indexs[i].pop();
							return;
						}
					}
				};
				for (int i = 0; i < s.length(); i++) {
					if ('*' == s[i]) { Del(); }
					else {
						indexs[s[i] - 'a'].emplace(i);
					}
				}				
				auto it = remove(s.begin(), s.end(), '*');
				s.erase(it, s.end());
				return s;
			}
		};;

单元测试

string s;
		TEST_METHOD(TestMethod11)
		{
			s = "aaba*";
			auto res = Solution().clearStars(s);
			AssertEx(string("aab"), res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "abc";
			auto res = Solution().clearStars(s);
			AssertEx(string("abc"), res);
		}