使用机器人打印字典序最小的字符串
难度:
标签:
题目描述
代码结果
运行时间: 82 ms, 内存: 18.5 MB
/*
思路:
1. 使用Java Stream API进行字符串的处理。
2. 将字符串 s 转换为字符流,利用栈操作并收集结果。
3. 实现同样的逻辑,但使用更函数式的方法。
*/
import java.util.Stack;
import java.util.stream.IntStream;
public class Solution {
public String robotWithString(String s) {
Stack<Character> t = new Stack<>();
StringBuilder result = new StringBuilder();
int[] count = new int[26];
s.chars().forEach(c -> count[c - 'a']++);
s.chars().forEach(c -> {
t.push((char) c);
count[c - 'a']--;
while (!t.isEmpty() && isSmallest(t.peek(), count)) {
result.append(t.pop());
}
});
return result.toString();
}
private boolean isSmallest(char c, int[] count) {
return IntStream.range(0, c - 'a').noneMatch(i -> count[i] > 0);
}
}
解释
方法:
此题解的基本思路是使用两个辅助容器:一个动态数组 `ans` 用于存储最终结果,一个栈 `stk` 用于临时存储字符。算法从头到尾遍历字符串 `s`,每次找出 `s` 中剩余部分的最小字符,并将其加入到结果字符串 `ans` 中。若栈顶字符小于等于 `s` 中的最小字符,则将栈顶字符弹出并加入到 `ans`。接着,将 `s` 中最小字符之前的所有字符(不包括最小字符本身)加入到栈中。这样做可以保证栈 `stk` 中的字符始终保持相对有序,从而在每次从 `s` 中提取最小字符后,可以有效地将栈中较小的字符移入 `ans`。最后,将 `stk` 中剩余的字符逆序后加入到 `ans` 中,以保证字典序最小。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中,为什么选择将栈中小于等于最小字符的元素弹出并加入结果,这样做有什么特别的目的或优势?
▷🦆
算法实现中用到了`min(s)`和`s.rindex(mn)`,每次循环都要调用这些操作,这样的处理方式是否最优?有没有更高效的方法来获取最小字符及其索引?
▷🦆
在将最小字符之前的所有字符加入栈时,使用了`s[:i + 1].replace(mn, '')`,这种方式是否可能影响算法的效率?如果有,如何优化?
▷🦆
当栈和字符串`s`中都有字符时,如何决定是应该从栈中弹出字符还是继续处理字符串`s`?
▷