【力扣】2434.使用机器人打印字典序最小的字符串

1、题目描述：

2、测试用例：

3、解题思路

• 每次删除字符串s的第一个字符，可以将s看做队列，每次从头部出。
• 在t的尾端插入或删除，可以将t看做栈
• 栈顶元素出栈条件：①比即将入栈的元素小并且比s中剩下的还没有入栈的所有字符都小②s中已经没有字符

class Solution {
 public String robotWithString(String s) {
        //s从头开始遍历
        //t从尾部开始
        StringBuilder s1 = new StringBuilder(s);
        Stack<Character> t = new Stack<>();
        StringBuilder m = new StringBuilder();

        int i = 0;
        boolean isDoen = false; //用于判断第一个“最小的字符”是否入栈
        //找出最小字符
        char minChar = (char) s.chars().min().orElseThrow(()-> new RuntimeException("No minimum character found.")) ;

        while (i <  s.length()){
            char c = s.charAt(i);
            if(s.charAt(i) == minChar){
                isDoen = true;
                //在遇到第一个"最小字符"之前，都不入栈！！！
                m.append(s.charAt(i));
                s1.deleteCharAt(0);
                i++;
            }else {
                char minChar1 = (char) s1.chars().min().orElseThrow(()-> new RuntimeException("No minimum character found."));
                //将t中比s尾部小的元素弹出加在m末尾，直到第一个比s.char(i)大的字符
                while (!t.isEmpty() && t.peek() <= c && isDoen && t.peek() <= minChar1){
                    //在出栈之前还应判断剩下的元素是否还有比栈顶小的元素
                    m.append(t.pop());
                }
                //栈顶元素大于等于c，将c入栈
                t.push(c);
                s1.deleteCharAt(0);
                i++;
            }
        }

        //将t中剩余元素全部出栈
        while (!t.isEmpty()){
            m.append(t.pop());
        }



        return m.toString();
    }
}

4、效率改进

public String robotWithString(String s) {
        //s从头开始遍历
        //t从尾部开始
        int n = s.length();
        String s1 = s;
        Stack<Character> t = new Stack<>();
        StringBuilder m = new StringBuilder();

        //int i = 0;
        //boolean isDoen = false; //用于判断第一个“最小的字符”是否入栈
        //找出最小字符,统计每个位置之后（包括当前位置）的最小字符个数
        //char minChar = (char) s.chars().min().orElseThrow(()-> new RuntimeException("No minimum character found.")) ;
        //统计每个位置之后（包含当前）最小的字符
        char[] minFromRight = new char[n];
        minFromRight[n - 1] = s.charAt(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            minFromRight[i] = (char) Math.min(s.charAt(i), minFromRight[i + 1]);
        }
        for (int i = 0; i < n; i++){
            char c = s.charAt(i);
            while (!t.isEmpty() && t.peek() <= c && t.peek() <= minFromRight[i]){
                m.append(t.pop());
            }
            t.push(c);

        }

//        while (i <  s.length()){
//            char c = s.charAt(i);
//            if(s.charAt(i) == minChar){
//                isDoen = true;
//                //在遇到第一个"最小字符"之前，都不入栈！！！
//                m.append(s.charAt(i));
//                s1= s1.substring(1);
//                i++;
//            }else {
//                char minChar1 = (char) s1.chars().min().orElseThrow(()-> new RuntimeException("No minimum character found."));
//                //将t中比s尾部小的元素弹出加在m末尾，直到第一个比s.char(i)大的字符
//                while (!t.isEmpty() && t.peek() <= c && isDoen && t.peek() <= minChar1){
//                    //在出栈之前还应判断剩下的元素是否还有比栈顶小的元素
//                    m.append(t.pop());
//                }
//                //栈顶元素大于等于c，将c入栈
//                t.push(c);
//                s1= s1.substring(1);;
//                i++;
//            }
//        }

        //将t中剩余元素全部出栈
        while (!t.isEmpty()){
            m.append(t.pop());
        }



        return m.toString();
    }

4.1 改进点1

不断创建StringBuilder 并调用 deleteCharAt(0)从字符串头部删除字符，这种方式效率较低，因为每次删除操作都需要移动数组元素，时间复杂度为 O(n²)。

✅ 优化目标

• 避免频繁使用 deleteCharAt(0)。
• 使用索引遍历原字符串，避免修改原始字符串副本。
• 提高整体时间复杂度至 O(n)。

4.2 改进点2

多次调用 s1.chars().min() 导致重复扫描。
✅ 优化目标：改进使用该函数的方式，预处理一个 minFromRight 数组，保存从当前位置开始的最小字符

5、官方答案

class Solution {
    public String robotWithString(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }

        Stack<Character> stack = new Stack<>();
        StringBuilder res = new StringBuilder();
        char minCharacter = 'a';
        for (char c : s.toCharArray()) {
            stack.push(c);
            cnt[c - 'a']--;
            while (minCharacter != 'z' && cnt[minCharacter - 'a'] == 0) {
                minCharacter++;
            }
            while (!stack.isEmpty() && stack.peek() <= minCharacter) {
                res.append(stack.pop());
            }
        }
        
        return res.toString();
    }
}