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(n2)。
? 優化目標
- 避免頻繁使用 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();}
}
