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])
}
执行结果如下：