字典序是指从前到后比较两个字符串大小的方法。首先比较第1个字符,如果不同则第1个字符较小的字符串更小,一直这样子比较下去。
比如:
s1:ABCDE
和 s2:ABCCE
两个字符串,s1的 D 比 s2的 C要更加大一点,所以s1 > s2。
现在有这样一个问题,
给定长度为N的字符串S,要构造一个长度为 N 的字符串 T。起初 ,T 是一个空串,随后反复进行下列任意操作,
- 从 S 的头部删除一个字符,加到 T 的尾部。
- 从 S 的尾部删除一个字符,加到 T 的尾部。
目标是构造字典序最小的字符串 T。
这类题型一般利用贪心来做,贪心就是就是遵循某种规则,不断贪心地选取当前的最优策略的算法。
每做出的一步选择都是当前的最优策略,并不需要考虑整体,但难点就在于当前最优策略的选择,拿上面那道题继续分析,
要创建字典序最小的字符串T,我们只需要保证字符串的前面尽量较小,所以每次从字符串 S 的首尾取相对较小的加入到字符串 T 中,这就是策略,但这个策略还可能遇到一个问题,如果当首尾的字符此时相等的话,该如何选择?这时候就要比较下一个了,选择下一个字符里面相对较小的加入到字符串 T 中。这两者结合就是我们的贪心策略。
有点懵?
不急,我们来看看图解。
假定给定的字符串 S = “ACDBCB”,
一开始,两指针指向字符串 S 的首尾,比较两者的大小,将小的一位加入到字符串 T 中,
此时两指针对应的字符相等,这时候要判断下一位的大小,
B < D,所以将右侧的先加入,
应该够清晰了吧,那么我们可以写一下伪代码了,伪代码主要是总结以上思路,以便更好的转换成最终代码。
1 | # String S; |
好,以上应该都比较好理解了,那可以直接转成我们的代码了。
1 | class Solution { |
整理于 2020.4.19