包含全部字符的无重最小字典序子序列

shaowu459

题目描述如下：

给定一个全部由小写英文字母组成的字符串s，要求返回 s 字典序最小的子序列组成的字符串，该子序列包含 s中的所有不同字符，且只包含一次，同时要求字典序最小。
也即，需要将s中的所有小写字母去重，去重时保留的字符不改变在原字符串s中的相对位置顺序，同时字典序最小。
题目要求也可以理解为在字符串s中删除一些字符，剩余的字符串包含s中的所有不同字符，没有重复重复字符，且字典序最小。

例如字符串bcacb，去重后能变成bca（位置是1、2、3）、bac（位置是1、3、4）、cab（位置是2、3、5）、acb（位置是3、4、5）四种字符串，最小字典序字符串是acb。

shaowu459

分析题意可知，最后要求的字符串左侧的字符应该是尽可能比右侧字符小，并且无重复。因此，我们可以从左到右遍历字符串，然后维护一个单调递增栈（最终不是标准的单调递增栈），通过判断决定当前遍历的字符如何处理。下面以字符串“zbcabcz”为例来说明整个分析过程。

遍历第一个字符z时，因为栈中还没有任何元素，因此z直接入栈：


遍历第二个字符b时，因为b小于z，如果能把b挪动到z前面去的话，结果字符串就会更小。那么，什么情况下才能把b挪动到前面去呢？因为最终字符串要包含所有字符，如果b后面没有z了，那么z只能保留在b前面，如果b后面有z这个字符，那么就可以把z去掉，让b排在前面，因为z可以在后面再添加，这样字符串就更小了。观察一下，因为b后面有z，所以把z弹出，让b进栈。


遍历第三个字符c时，因为c大于b，所以可以直接入栈，放在b下面。


遍历第四个字符a时，因为a小于c，当前栈内有b和c，并且观察a后面还有b和c，所以同样可以把b和c做出栈处理，把a入栈，因为b和c可以后面再添加。


遍历第五个字符b时，因为b大于a，因此直接入栈：


后面同理，c和z陆续入栈：



最后，使用文本函数将最终栈内数组合并起来即可。

shaowu459

通过上面的分析，我们可以总结公式思路如下：
1）从左到右遍历s中的每个字符，模拟一个非标准的单调递增栈。
2）如果当前字符大于栈底的字符，当前字符直接加在栈底。
3）如果当前字符小于栈底元素，那么就从栈底开始往上遍历栈内已有元素（直至栈为空或者栈底元素小于当前字符），但需同时考虑以下两种情况：如果栈底已有字符大于当前遍历的字符且在当前字符后面还有出现，那么就弹出栈，因为后面可以再添加；如果栈内字符大于当前字符，但在后面没有了，就不能做出栈处理了，因为要保证所有字符都在结果中出现。遍历完毕后，将当前字符追加在栈底。
4）因为维护的是一个单调递增栈，所以当前字符在栈内已经出现时，可以不做任何处理。
5）遍历完毕后，将栈内元素连接起来生成结果字符串。

shaowu459

参考公式如下：

1. =CONCAT(REDUCE("",SEQUENCE(LEN(A2)),LAMBDA(x,y,LET(s,MID(A2,y,1),IF(OR(s=x),x,VSTACK(IF(s>@TAKE(x,-1),x,REDUCE(x,x,LAMBDA(m,n,LET(t,@TAKE(m,-1),DROP(m,-(s<t)*ISNUMBER(FIND(t,MID(A2,y,LEN(A2))))))))),s))))))

复制代码

shaowu459

公式简要说明如下：

=CONCAT(    合并栈内元素
    REDUCE(
        "",     设定x初始值为空字符串，防止弹出所有栈内元素时出错。x即为模拟的单调递增栈
        SEQUENCE(LEN(A2)),     生成1~字符串长度的序列
        LAMBDA(x, y,
            LET(
                s, MID(A2, y, 1),     按顺序提取源字符串中每个字符
                IF(
                    OR(s = x),     如果当前字符在栈内已经存在
                    x,     不执行任何操作，保留x不变
                    VSTACK(     纵向堆积公式产生的结果
                        IF(
                            s > @TAKE(x, -1),     如果当前字符大于x底端的字符
                            x,     保留x不变，追加s在x底端
                            REDUCE(
                                x,     逐个判断当前栈内元素是否需要出栈
                                x,     控制次数
                                LAMBDA(m, n,
                                    LET(
                                        t, @TAKE(m, -1),     提取出栈后的底端元素
                                        DROP(m, -(s < t) * ISNUMBER(FIND(t, MID(A2, y, LEN(A2)))))   如果栈底端元素大于当前字符，并且在当前字符后面还有，就出栈
                                    )
                                )
                            )
                        ),
                        s     无论栈内元素是否做出栈处理，最后都要在栈底追加当前遍历的字符
                    )
                )
            )
        )
    )
)

沈默00

向版主学习....

shaowu459

沈默00 发表于 2023-12-21 17:56
向版主学习....

帖子里如果有描述不清晰或错误的，还请指正

橒♂蝣

reduce函数最难理解的就是vstack累加器这样的，相关于自身调用

shaowu459

海鲜版主简化公式，直接提取x里需要的行数：=CONCAT(REDUCE("",SEQUENCE(LEN(A2)),LAMBDA(x,y,LET(s,MID(A2,y,1),IF(OR(s=x),x,VSTACK(TAKE(x,MATCH(1,{0}/ISERR(FIND(x,A2,y/(s<x))))),s))))))

shaowu459

橒♂蝣 发表于 2023-12-22 11:51
reduce函数最难理解的就是vstack累加器这样的，相关于自身调用

对，就是对x的各种操作和运用。x里已有信息可以后续调用