本文共 1181 字，大约阅读时间需要 3 分钟。

如何找到给定字符串的最小字典序子序列？

在解决这个问题时，我们需要找到一个最小的字典序的子序列，长度为k。这个问题可以通过使用单调栈的方法来高效解决。

解决思路

我们可以使用单调栈的方法来找到最小字典序的子序列。具体步骤如下：

这种方法确保了我们总是选择当前最小的字典序字符，时间复杂度为O(n)，空间复杂度为O(n)。

代码实现

以下是实现该算法的Java代码示例：

public class Solution {    public String deleteChar(String str, int k) {        if (k <= 0) {            return "";        }        int remaining = str.length() - k;        StringBuilder sb = new StringBuilder();        for (int i = 0; i < str.length(); i++) {            char c = str.charAt(i);            while (sb.length() > 0 && sb.charAt(sb.length() - 1) > c && remaining > 0) {                sb.setLength(sb.length() - 1);                remaining--;            }            sb.append(c);        }        if (remaining > 0) {            sb.setLength(sb.length() - remaining);        }        return sb.toString();    }}

代码解释

• 初始化检查：如果k为0或负数，直接返回空字符串。
• 计算删除数量：计算需要删除的总字符数。
• 遍历字符串：逐个处理字符串中的每个字符。
• 维护栈单调性：对于每个字符，检查栈顶是否需要删除，确保结果字符串的字典序最小。
• 处理剩余删除数量：在遍历结束后，若仍有删除需求，调整结果字符串长度。

这种方法高效且简洁，能够在O(n)时间复杂度内解决问题，适用于处理较长字符串的情况。

转载地址：http://dhds.baihongyu.com/