Readme

2434.Using-a-Robot-to-Print-the-Lexicographically-Smallest-String

翻译一下题目的意思。我们从头到尾扫一遍原串s，依次将每个字符放入一个辅助的栈，但是栈顶的弹出时机可以自定义。问最终从栈弹出的字符串的最小字典序。

入手时，我们采用贪心的思想，思考如果s中有一个字符a在位置i处，它一定应该是最终答案的首字符。所以我们在遇到a之前，所有的字符，即s[0:i-1]都应该依次存入栈但是不弹出。直至遇到那个a，将其放入栈顶后马上弹出，这样才能得到一个以a开头的最小字典序字符串。

此时，我们需要考虑的是s[i+1]，并且注意到之前的s[0:i-1]已经逆序存于栈顶。此时我们的两个选择是：立即弹出当前的栈顶元素，或者将s[i+1]压入栈顶（然后立即弹出，或者保留观望）。此时的决策依据显然就是：此时栈顶元素的字符是否够小？如果s[i+1]及其它之后全局最小的字符（假设还是a，位置在j），它比栈顶元素还要小，那么根据贪心的原则，我们必然至少要继续进行入栈的操作，直至遇到s[j]。接下来就是一个入栈+出栈，就将s[j]打印出来。反之，如果s[i+1]及其它之后全局最小的字符，比当前的栈顶元素还要大，那么打印当前的栈顶元素自然是最合算的策略。

所以本题需要预处理一个后缀数组nextSmallest，其中nextSmallest[i]表示[i:n-1]里面最小的字符。这样当我们处理到s[i]的时候，就可以用nextSmallest[i]和栈顶元素进行比较，来判断是否要持续入栈，还是可以弹出栈顶元素直接打印。