[数据结构与算法]LeetCode 2434(贪心+栈+动态规划)

题目链接：LeetCode 2434. 使用机器人打印字典序最小的字符串

题目描述：

给你一个字符串 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$=“” 。

提示一：
可以把机器人的空字符串t看成一个空栈，相当于求一个最小的出栈顺序。

提示二：
贪心的想一下，如果栈顶元素出站的前提是什么？如果字符串s中从遍历到的当前字符开始后面的字符没有比当前栈顶元素小的时候，是不是当前的栈顶元素就可以出栈了， 如果后面还有比栈顶元素小的字符，那么把它放到前面一定会更小，所以要一直遍历到比栈顶元素小的字符。
总结：栈顶元素$\le$后续字符(未入栈)，那么栈顶元素可以出栈加入到ans(答案)字符串中。

提示三：
怎么可以求某一个位置后面的最小字符呢？ 每次循环遍历一次肯定是不可行的，时间肯定会超时。
为了快速的知道某一个位置后面的最小字符，可以利用动态规划来实现，按字符串s逆序跑一遍O(n)，$f[i]$:表示i位置以及后面的最小字符。
$f[i]=min(s[i],f[i+1])$就可以求出。

提示四：
最后要把栈中剩下的元素放入ans(答案)中。

时间复杂度：O(n+m),n为字符串s的长度,m为栈的元素个数

代码实现(C++)：

class Solution {
public:
    char f[100010];
    stack<char> stk;
    string robotWithString(string s) {
        f[s.size()]='z'+1;
        for(int i=s.size()-1;i>=0;i--){
            f[i]=min(s[i],f[i+1]);
        }

        string ans="";

        for(int i=0;i<s.size();i++){
            while(stk.size() && stk.top()<=s[i] && stk.top()<=f[i]){
                char t=stk.top();
                stk.pop();
                ans.push_back(t);
            }
            stk.push(s[i]);
        }

        while(stk.size()){
            char t=stk.top();
            stk.pop();
            ans.push_back(t);
        }

        return ans;
    }
};