leetcode
leetcode 2101 ~ 2150
使用机器人打印字典序最小的字符串

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

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在算法中,为什么选择将栈中小于等于最小字符的元素弹出并加入结果,这样做有什么特别的目的或优势?
在算法中选择将栈中小于等于最小字符的元素弹出并加入结果的做法,主要是为了保证结果字符串的字典序最小。栈用于暂存字符,并可以通过控制字符的入栈和出栈顺序来确保最终结果的有序性。当栈顶的字符小于等于字符串s中未处理部分的最小字符时,意味着栈顶的字符在字典序上不可能被后来的任何字符替代为更小,因此可以安全地将其加入到结果字符串中,从而确保整体上的字典序最小化。
🦆
算法实现中用到了`min(s)`和`s.rindex(mn)`,每次循环都要调用这些操作,这样的处理方式是否最优?有没有更高效的方法来获取最小字符及其索引?
虽然使用`min(s)`和`s.rindex(mn)`可以直接定位到最小字符及其最后一个索引,这种方法简单直观,但每次循环调用这些操作会导致时间复杂度较高,特别是对于长字符串效率不是最优。一种更高效的方法是使用优先队列(或称为最小堆)来跟踪未处理字符串中的每个字符及其索引,这样可以在对数时间内找到当前最小的字符和它的索引,从而提高整体算法的效率。
🦆
在将最小字符之前的所有字符加入栈时,使用了`s[:i + 1].replace(mn, '')`,这种方式是否可能影响算法的效率?如果有,如何优化?
使用`s[:i + 1].replace(mn, '')`确实可能影响算法的效率,因为这种方法在每次循环中都会进行一次字符串切片操作和一次字符替换操作,这两者都是线性时间复杂度的操作。一个优化方法是在一开始就使用一个计数数组来记录每个字符的出现次数,然后根据需要更新计数并直接从计数数组中决定哪些字符应该入栈,避免了不必要的字符串操作,从而提高效率。
🦆
当栈和字符串`s`中都有字符时,如何决定是应该从栈中弹出字符还是继续处理字符串`s`?
在栈和字符串`s`都有字符的情况下,决策依据是栈顶元素与`s`中剩余部分的最小字符的比较。如果栈顶元素小于或等于`s`中的最小字符,那么应该从栈中弹出字符并将其加入到结果字符串中,因为这样可以保持结果的字典序最小。如果栈顶元素大于`s`中的最小字符,那么应该继续处理字符串`s`,将新的字符按逻辑加入栈中,直到可以安全地移动栈顶元素到结果中。

相关问题