小红书0827笔试

第一题：因为最少连续三个所以我们直接暴力然后如果连续三个乘积大于n退出判断，是n的立方根复杂度
第二题：右端点排序，然后贪心尽可能找是否重合，不重合就答案+1
第三题：一共要确定 i-k,i,j,j+k四个点对吧，我们可以先去找i-k和i，怎么去找i-k和i呢，其实就是从左往右找第一个逆序对，比如zbaba,（下标从1开始）那第一个逆序对就是下标为1和1之后字符小于z的值，所以i-k已经确定了是下标为1。然后我们再考虑怎么去找i，那我们首先肯定要找字典序最小的字符，在例子中就是a，如果有多个a，我们就要找能换且最靠后的a(因为我们还要考虑j,j+k，如果k太大可能后面不存在j，j+k)。找到最后一个a那我们已经确定i-k,i了。我们只要从i+1开始找第一个[j,j+k]的逆序对，如果不存在j,j+k的逆序对，那我们只需要换n-k,n就好了（可以感性理解一下）。时间复杂度为 O(n)