第二题
给出一个数组 A，找到最大的 A[i] - A[j]，要求 i > j。
题解
这题很简单，直接遍历每个 A[i]，维护它前面最小的那个数 minn，然后求出最大的 A[i] - minn 就行了。
代码
第三题
给定一个字符串，对该字符串进行删除操作，保留 k 个字符且相对位置不变，使字典序最小。
题解
这题也脑抽了，想了一堆方法，dp 复杂度太高，线段树太麻烦，最后用 map 勉强写了一下。
主要思想是这样的，最后要保留 k 个字符，那么第一个字符只能在下标 0 ~ n-k 中寻找，那肯定找最小的啊，如果有多个就找最前面那个，把它的位置记为 pos。
然后第二个字符肯定得在下标 pos ~ n-k+1 中寻找，还是一样的思路，找到以后更新 pos 位置，依次找下去找到 k 个为止。
所以我就利用了 map 的特性，把寻找窗口内的字符个数做一下统计，然后取出 map 中的第一个字符就是字典序最小的了，次数减一，如果减到 0 了就删除掉。
然后从 pos 位置开始遍历，直到第一个等于你刚刚取出的字符为止，更新 pos 位置。
最终的时间复杂度是 ，可以直接看作 。
最优解：
最优解当时没想出来，是用单调栈。维护一个递增的单调栈，我们的目标是保留 k 个字符，也就是删除 n-k 个字符。
那么如果栈顶元素大于当前遍历元素，并且还没删够 n-k 个，就出栈，当作删除了一个元素。否则的话如果删够了，不管大小关系统统入栈，因为你没法删了。
最后全遍历完了，如果还没删够，那就继续出栈，直到删够为止。最后把栈里的字符拼接成一个字符串就是答案了。
时间复杂度是 的。
代码
最优解：
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
我的微信：weiyang792321264。有任何问题都可以在评论区留言，也欢迎加我微信深入沟通~
本文分享自微信公众号 - 算法码上来（GodNLP）。
如有侵权，请联系 [email protected] 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。