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

题目地址：

给定一个小写英文字母组成的字符串，再给定一个数字$k$，求其最小字典序的长度为$k$的子序列。

这个题目的思路与完全一样，只需要把一个字符串看成是$27$进制的整数即可，然后同样用单调栈来做。代码如下：

public class Solution {       /**     * @param str: the string     * @param k: the length     * @return: the substring with  the smallest lexicographic order     */    public String deleteChar(String str, int k) {           // Write your code here.        if (k == 0) {               return "";        }                k = 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 && k > 0) {                   sb.setLength(sb.length() - 1);                k--;            }                        sb.append(c);        }                if (k > 0) {               sb.setLength(sb.length() - k);        }                return sb.toString();    }}

时空复杂度$O(n)$。

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