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

福大大架构师每日一题

发布于 2021-12-04 08:48:03

1.1K00

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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

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

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

时间复杂度：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])
}