[LeetCode] 2434. Using a Robot to Print the Lexicographically Smallest String

You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty:

Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.

Remove the last character of a string t and give it to the robot. The robot will write this character on paper.

Return the lexicographically smallest string that can be written on the paper.

Example 1:
Input: s = “zza”
Output: “azz”
Explanation: Let p denote the written string.
Initially p=””, s=”zza”, t=””.
Perform first operation three times p=””, s=””, t=”zza”.
Perform second operation three times p=”azz”, s=””, t=””.

Example 2:
Input: s = “bac”
Output: “abc”
Explanation: Let p denote the written string.
Perform first operation twice p=””, s=”c”, t=”ba”.
Perform second operation twice p=”ab”, s=”c”, t=””.
Perform first operation p=”ab”, s=””, t=”c”.
Perform second operation p=”abc”, s=””, t=””.

Example 3:
Input: s = “bdda”
Output: “addb”
Explanation: Let p denote the written string.
Initially p=””, s=”bdda”, t=””.
Perform first operation four times p=””, s=””, t=”bdda”.
Perform second operation four times p=”addb”, s=””, t=””.

Constraints:
1 <= s.length <= 105
s consists of only English lowercase letters.

使用机器人打印字典序最小的字符串。

给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

• 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
• 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。

请你返回纸上能写出的字典序最小的字符串。

思路

思路是贪心，需要用到 stack。

注意题目的操作规则，从 s 中删除字母只能从左开始，字母加给 t，从 t 中删除字母只能从右开始写到纸上。对于 t 的字母来说，是先进后出。那么比较容易想到用 stack，从 s 中每删除一个字母，就往 stack 里放。

这里我们需要创建一个和 input 字符串等长的数组，记为 minCharFrom，记录一下每个字母的右边是否存在一个比它小的字母。这样在往 stack 里放字母时，就可以判断当前字母是否可以放入 stack 中。

开始遍历 input 字符串，对于每一个字母 cur ，如果他的右边没有比他更小的字母了，则把他们从 stack 中弹出，加到结果字符串中。最后如果 stack 中还有剩余字母，也把它们加到结果字符串中。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String robotWithString(String s) {
        int n = s.length();
        // 预处理：从后往前记录每个位置起始的最小字符
        char[] minCharFrom = new char[n];
        minCharFrom[n - 1] = s.charAt(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            minCharFrom[i] = (char) Math.min(s.charAt(i), minCharFrom[i + 1]);
        }

        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            stack.push(s.charAt(i));
            // 把栈中尽可能小的字符都弹出
            while (!stack.isEmpty() && stack.peek() <= minCharFrom[i == n - 1 ? i : i + 1]) {
                sb.append(stack.pop());
            }
        }

        // 栈中剩余的字符也弹出
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}