当前位置：首页 > news >正文

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

news 2025/6/8 5:17:09

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();}
}