Medium

题目描述

给你一个字符串 s 和一个机器人，该机器人当前持有一个空字符串 t。执行下述操作之一，直到 s 和 t 都变成空字符串：

  • 删除字符串 s 的第一个字符，并将该字符给机器人。机器人把这个字符添加到字符串 t 的末尾。
  • 删除字符串 t 的最后一个字符，并将该字符给机器人。机器人将该字符写到纸上。

请返回纸上能写出的字典序最小的字符串。

示例 1：

输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
初始状态 p=""，s="zza"，t=""
执行第一种操作三次 p=""，s=""，t="zza"
执行第二种操作三次 p="azz"，s=""，t=""

示例 2：

输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一种操作两次 p=""，s="c"，t="ba"
执行第二种操作两次 p="ab"，s="c"，t=""
执行第一种操作一次 p="ab"，s=""，t="c"
执行第二种操作一次 p="abc"，s=""，t=""

示例 3：

输入：s = "bdda"
输出："addb"
解释：用 p 表示写出来的字符串。
初始状态 p=""，s="bdda"，t=""
执行第一种操作四次 p=""，s=""，t="bdda"
执行第二种操作四次 p="addb"，s=""，t=""

约束条件：

  • 1 <= s.length <= 10^5
  • s 只包含英文小写字母

提示：

  • 如果字符串中有一些字符 “a”，它们可以在其他任何字符之前被写到纸上
  • 最后一个 “a” 之前字符串中的每个字符都应该以相反的顺序写出
  • 在机器人将每个 “a” 写到纸上后，对于其他字符 “b”、“c” 等也是如此

解题思路

这是一个贪心 + 栈的问题。核心思想是利用栈的后进先出特性来实现字符的重新排序。

分析过程：

  1. 预处理阶段：我们需要知道从每个位置开始，后面还有哪些字符可用。这样可以帮助我们决定是否应该立即输出栈顶字符。

  2. 贪心策略：

    • 遍历字符串 s，将字符依次压入栈 t
    • 在每次压栈后，检查栈顶字符是否应该立即输出
    • 如果栈顶字符小于等于后续所有字符中的最小字符，则应该输出

  3. 具体实现：

    • 首先统计每个字符的出现次数
    • 维护一个 min_char 变量，表示剩余字符中的最小字符
    • 遍历字符串时，将字符压入栈，同时更新字符计数
    • 当栈不为空且栈顶字符小于等于剩余字符的最小值时，弹出栈顶并加入结果

这种方法确保我们总是优先输出较小的字符，从而得到字典序最小的结果。

代码实现

class Solution {
public:
    string robotWithString(string s) {
        int n = s.length();
        vector<int> count(26, 0);
        
        // 统计每个字符的出现次数
        for (char c : s) {
            count[c - 'a']++;
        }
        
        string result = "";
        string t = "";  // 栈
        char min_char = 'a';
        
        for (char c : s) {
            // 将当前字符压入栈
            t.push_back(c);
            count[c - 'a']--;
            
            // 更新剩余字符中的最小字符
            while (min_char <= 'z' && count[min_char - 'a'] == 0) {
                min_char++;
            }
            
            // 如果栈顶字符小于等于剩余字符的最小值，则弹出
            while (!t.empty() && t.back() <= min_char) {
                result += t.back();
                t.pop_back();
            }
        }
        
        // 输出栈中剩余的所有字符
        while (!t.empty()) {
            result += t.back();
            t.pop_back();
        }
        
        return result;
    }
};

class Solution:
    def robotWithString(self, s: str) -> str:
        from collections import Counter
        
        count = Counter(s)
        result = []
        t = []  # 栈
        min_char = 'a'
        
        for c in s:
            # 将当前字符压入栈
            t.append(c)
            count[c] -= 1
            if count[c] == 0:
                del count[c]
            
            # 更新剩余字符中的最小字符
            while min_char <= 'z' and min_char not in count:
                min_char = chr(ord(min_char) + 1)
            
            # 如果栈顶字符小于等于剩余字符的最小值，则弹出
            while t and t[-1] <= min_char:
                result.append(t.pop())
        
        # 输出栈中剩余的所有字符
        while t:
            result.append(t.pop())
        
        return ''.join(result)

public class Solution {
    public string RobotWithString(string s) {
        int[] count = new int[26];
        
        // 统计每个字符的出现次数
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        StringBuilder result = new StringBuilder();
        Stack<char> t = new Stack<char>();
        char minChar = 'a';
        
        foreach (char c in s) {
            // 将当前字符压入栈
            t.Push(c);
            count[c - 'a']--;
            
            // 更新剩余字符中的最小字符
            while (minChar <= 'z' && count[minChar - 'a'] == 0) {
                minChar++;
            }
            
            // 如果栈顶字符小于等于剩余字符的最小值，则弹出
            while (t.Count > 0 && t.Peek() <= minChar) {
                result.Append(t.Pop());
            }
        }
        
        // 输出栈中剩余的所有字符
        while (t.Count > 0) {
            result.Append(t.Pop());
        }
        
        return result.ToString();
    }
}

var robotWithString = function(s) {
    const count = new Array(26).fill(0);
    
    // 统计每个字符的出现次数
    for (const c of s) {
        count[c.charCodeAt(0) - 97]++;
    }
    
    let result = "";
    const t = []; // 栈
    let minChar = 'a';
    
    for (const c of s) {
        // 将当前字符压入栈
        t.push(c);
        count[c.charCodeAt(0) - 97]--;
        
        // 更新剩余字符中的最小字符
        while (minChar <= 'z' && count[minChar.charCodeAt(0) - 97]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：O(n)，其中 n 是字符串长度。每个字符最多被压入栈一次和弹出栈一次
  • 空间复杂度：O(n)，主要用于栈存储字符，最坏情况下栈中存储所有字符

相关题目