网站 简约,网络营销运营策划,网络公司企业网站源码,电子产品网站模板https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/ 给你一个字符串 s 和一个机器人#xff0c;机器人当前有一个空字符串 t 。执行以下操作之一#xff0c;直到 s 和 t 都变成空字符串。请你返回纸上能写出的字典序最小的… 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 szza t 。
执行第一个操作三次得到 p s tzza 。
执行第二个操作三次得到 pazz s t 。
示例 2输入s bac
输出abc
解释用 p 表示写出来的字符串。
执行第一个操作两次得到 p sc tba 。
执行第二个操作两次得到 pab sc t 。
执行第一个操作得到 pab s tc 。
执行第二个操作得到 pabc s t 。
示例 3输入s bdda
输出addb
解释用 p 表示写出来的字符串。
一开始p sbdda t 。
执行第一个操作四次得到 p s tbdda 。
执行第二个操作四次得到 paddb s t 。提示
1 s.length 105
s 只包含小写英文字母。题解 有一个初始为空的栈t给定字符的入栈顺序求字典序最小的出栈序列。因为是最小的字典序列所以本题可以使用贪心策略。 对于任意时刻当前可供选择的字符包括栈顶元素(如果栈非空)没有入栈的元素当前索引i及之后的全部元素我们从这两个元素中选取最小值进行操作
class Solution {
public:string robotWithString(string s) {int n s.size();string res;stackchar t;// 用一个数组来记录索引i到结尾的最小元素vectorchar min_i2end(n);min_i2end[n - 1] s[n - 1];for (int i n - 2; i 0; --i) {min_i2end[i] min(min_i2end[i 1], s[i]);}for (int i 0; i n; i) {// 如果后续没有更小的值了那么就将栈顶元素写入结果while (!t.empty() t.top() min_i2end[i]){res.push_back(t.top());t.pop();}// 否则入栈t.push(s[i]);}// 后处理while (!t.empty()) {res.push_back(t.top());t.pop();}return res; }
};
