LeetCode 456: “132” Pattern

这个题是昨晚上回寝室前赶出来的,因为看到是Medium而且感觉不难(实际也不难)。

原题:https://leetcode.com/problems/132-pattern

题目意思是,判断一个数组是否包含子序列ai、aj、ak(i<j<k),满足ai<ak<aj

好像跟一般领奖台是反着的,但是可以直观理解题意。
好像跟一般领奖台是反着的,但是可以直观理解题意。

主算法

思路是遍历每一个可能的k值,然后找到它之前第一个(也就是距离最近的)比它大的数作为aj,然后再判断a0~aj-1之间的最小值是否小于ak

之所以要找到“第一个”比它大的数,理由也很明显:要尽量扩大找ai的范围,否则可能会有false negative的情况。

思路很简单,关键是如何做到O(n)。因为遍历每一个k的过程就是O(n)的,所以要求后面两个步骤都是O(1),也就是要预处理。预处理最小值很简单,开一个数组记录一下即可,空间复杂度O(n)。预处理“之前第一个比ak大的数(的位置)”就比较麻烦了,放在子算法里说,空间复杂度也是O(n)。

因此最终算法分三步:预处理a0~aj的最小值,预处理ak之前第一个大的数,遍历每一个可能的k。

子算法

要预处理每个数之前第一个比它大的数,用到了之前一个stack的奇技淫巧。方法是维护一个pair<数, 位置>的stack,其中数是递减的;对于数组从头到尾遍历,每个数先将栈顶比它小的数pop出去,如果pop完了栈空了,说明前面没有比它大的数,此时预处理结果为-1;否则预处理结果为栈顶数的位置。处理完之后将当前pair<数, 位置>也push进栈。

原理:因为要找到之前第一个比它大的数,如果栈顶的数比当前数还小,那对于它们之后的数来说,当前数更可能是比后面数大的结果,所以将栈顶pop出去。因为每个数最多进出栈一次,时间复杂度O(n)。

C++代码

因为写的很赶,好多边界都没care,其实应该还有能优化的地方(因为运行时间才到beat 55%的位置……)

发表评论

电子邮件地址不会被公开。 必填项已用*标注