解题思路

这道题的目标是判断是否存在三个下标 $i<j<k$，满足：

$nums[i] < nums[k] < nums[j]$

这就是经典的 $132$ 模式判断问题。

一个直接想法是枚举三个位置，但时间复杂度是 $O(n^3)$，显然无法通过 $n \le 2\times 10^5$ 的数据范围。

题目描述

给定一个长度为 $n$ 的整数数组 $nums$，请判断数组中是否存在满足下列条件的三个下标 $i,j,k$：

• $i < j < k$
• $nums[i] < nums[k] < nums[j]$

如果存在这样的三元组，则称数组中存在一个 132 模式。

请输出是否存在 $132$ 模式。

输入描述

第一行输入一个整数$n$，表示数组长度。

第二行输入$n$个整数，表示数组$nums$。

输出描述

如果数组中存在 132 模式，输出 true；否则输出 false。

样例一

输入

4
1 2 3 4

输出

false

说明

数组中不存在满足条件的三元组。

样例二

输入

4
3 1 4 2

输出

true

说明

存在一组满足条件的下标，对应的三个数为 $(1,4,2)$，满足： $(1 < 2 < 4)$

因此存在 $132$ 模式。

样例三

输入

4
-1 3 2 0

输出

true

说明

数组中存在 $132$ 模式，例如：

$(-1,3,2)$ $(-1,3,0)$ $(-1,2,0)$

数据范围

$(1 \le n \le 2 \times 10^5)$ $(-10^9 \le nums[i] \le 10^9)$