2434. Using a Robot to Print the Lexicographically Smallest String

[Woodyiiiiiii]

这道题的思路是：每次找到未遍历过的最小字母的位置，然后加入进stack中，对比stack顶部和字母的两者的大小。

如果按照非常直接的思路，做法如下，相当长，时间复杂度也到了O(nlogn).

class Solution {
    public String robotWithString(String s) {
        StringBuilder res = new StringBuilder();
        StringBuilder stack = new StringBuilder();
        char minChar = 'z';
        int n = s.length();
        int k = 0;

        PriorityQueue<Pair> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.c == o2.c) {
                return o1.idx - o2.idx;
            } else {
                return o1.c - o2.c;
            }
        });
        for (int i = 0; i < n; i++) {
            pq.add(new Pair(s.charAt(i), i));
        }

        while (k < n) {
            int idx = k;
            boolean find = false;
            while (!pq.isEmpty()) {
                Pair peek = pq.peek();
                if (peek.idx < k) {
                    pq.poll();
                    continue;
                }
                if (peek.c < minChar) {
                    minChar = peek.c;
                    idx = peek.idx;
                    find = true;
                    pq.poll();
                }
                break;
            }
            if (find || stack.length() == 0) {
                String minStr = s.substring(k, idx + 1);
                k = idx + 1;
                stack.append(minStr);
            }
            res.append(stack.charAt(stack.length() - 1));
            stack.deleteCharAt(stack.length() - 1);
            minChar = stack.length() == 0 ? 'z' : stack.charAt(stack.length() - 1);
        }

        return res.append(stack.reverse()).toString();
    }
}

class Pair {

    char c;
    int idx;

    public Pair(char c, int idx) {
        this.c = c;
        this.idx = idx;
    }

}

但如果用贪心的做法，可以类似双指针的思想，idx变量指向未遍历的最小字母的位置，另一个指针指向遍历的位置。同步更新。用stack。与上述我自己的做法不同的是，在如何找到未遍历的下一个最小字母位置这点上，此法直接使用计数数组。

class Solution {
    public String robotWithString(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        StringBuilder res = new StringBuilder();
        // i之后的最小字符
        int idx = 0;
        while (idx < 26 && cnt[idx] == 0) {
            ++idx;
        }

        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            cnt[c - 'a']--;
            stack.addLast(c);
            while (idx < 26 && cnt[idx] == 0) {
                idx++;
            }

            while (!stack.isEmpty() && stack.peekLast() - 'a' <= idx) {
                res.append(stack.pollLast());
            }
        }

        if (!stack.isEmpty()) {
            while (!stack.isEmpty()) {
                res.append(stack.pollLast());
            }
        }

        return res.toString();
    }
}

---

• https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string/