132pattern-Leetcode456
QUESTION: To search for a subsequence (s1,s2,s3
) such that s1 < s3 < s2
.
INTUITION: Suppose we want to find a 123
sequence with s1 < s2 < s3
, we just need to find s3
, followed by s2
and s1
. Now if we want to find a 132
sequence with s1 < s3 < s2
, we need to switch up the order of searching. we want to first find s2
, followed by s3
, then s1
.
DETECTION: More precisely, we keep track of highest value of s3
for each valid (s2 > s3)
pair while searching for a valid s1
candidate to the left. Once we encounter any number on the left that is smaller than the largest s3
we have seen so far, we know we found a valid sequence, since s1 < s3
implies s1 < s2
.
ALGORITHM: We can start from either side but I think starting from the right allow us to finish in a single pass. The idea is to start from end and search for valid (s2,s3)
pairs, we just need to remember the largest valid s3
value, using a stack
will be effective for this purpose. A number becomes a candidate for s3
if there is any number on the left bigger than it.
CORRECTNESS: As we scan from right to left, we can easily keep track of the largest s3
value of all (s2,s3)
candidates encountered so far. Hence, each time we compare nums[i]
with the largest candidate for s3
within the interval nums[i+1]...nums[n-1]
we are effectively asking the question: Is there any 132 sequence with s1 = nums[i]
?Therefore, if the function returns false, there must be no 132 sequence.
IMPLEMENTATION:
- Have a
stack
, each time we store a new number, we firstpop
out all numbers that are smaller than that number. The numbers that arepopped
out becomes candidate fors3
. - We keep track of the
maximum
of suchs3
(which is always the most recentlypopped
number from thestack
). - Once we encounter any number smaller than
s3
, we know we found a valid sequence sinces1 < s3
impliess1 < s2
.
最新文章
- ViewPager循环显示
- 继电器是如何成为CPU的(2)
- 网站CSS写在html里面的好处
- Html-Css-div标签嵌套浮动div标签时无法撑开外部div的解决
- Java学习日记 集合
- ie 64bit调用activex控件
- linux下一个Oracle11g RAC建立(八)
- 挂载mount
- Ubuntu server 16.04的安装 以及配置(服务器版)
- C#线程安全使用(三)
- follow
- docker for windows 10 添加阿里云镜像仓库无效问题
- centos7更改网卡名
- ant design的一些坑
- SpringBoot整合Quartz定时任务 的简单实例 2
- js 数组的增删改查
- SV中的线程
- Ubuntu系统下Jenkins的本地构建基本方法
- springMVC 简单应用
- cobbler 无人值守系统安装