2021-12-02：给定一个字符串str，和一个正数k。 返回长度为k的所有子序列中，字典序最大的子序列。 来自腾讯。

答案2021-12-02：

单调栈。先进来的元素大，后进来的元素小。 时间复杂度：O(N)。 额外空间复杂度：O(N)。

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

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代码