2021-12-02：给定一个字符串str，和一个正数k。 返回长度为

2021-12-02：给定一个字符串str，和一个正数k。

返回长度为k的所有子序列中，字典序最大的子序列。

来自腾讯。

答案2021-12-02：

单调栈。先进来的元素大，后进来的元素小。

时间复杂度：O(N)。

额外空间复杂度：O(N)。

代码用golang编写。代码如下：

代码语言：txt复制

package main

import "fmt"

func main() {
    s := "abcba"
    k := 3
    ret := maxString(s, k)
    fmt.Println(ret)
}

func maxString(s string, k int) string {
    if k <= 0 || len(s) < k {
        return ""
    }
    str := []byte(s)
    n := len(str)
    stack := make([]byte, n)
    size := 0
    for i := 0; i < n; i   {
        for size > 0 && stack[size-1] < str[i] && size n-i > k {
            size--
        }
        if size n-i == k {
            ret := stack[0:size]
            ret = append(ret, s[i:]...)
            return string(ret)
        }
        stack[size] = str[i]
        size  
    }
    return string(stack[0:k])
}

执行结果如下：

图片

---

左神java代码

java 腾讯 字符串

0 人点赞