132-pattern

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array of <code>n</code> integers <code>nums</code>, a 132 pattern is a subsequence of three integers <code>nums[i]</code>, <code>nums[j]</code> and <code>nums[k]</code> such that <code>i &lt; j &lt; k</code> and <code>nums[i] &lt; nums[k] &lt; nums[j]</code>.

Return <code>true</code> if there is a 132 pattern in <code>nums</code>, otherwise, return <code>false</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
</pre>

Example 2:

<pre>
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
</pre>

Example 3:

<pre>
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 105</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
</ul>

find132pattern

132 Pattern

Stack

Array

Binary Search

Ordered Set

Monotonic Stack

给你一个整数数组 <code>nums</code> ，数组中共有 <code>n</code> 个整数。132 模式的子序列 由三个整数 <code>nums[i]</code>、<code>nums[j]</code> 和 <code>nums[k]</code> 组成，并同时满足：<code>i < j < k</code> 和 <code>nums[i] < nums[k] < nums[j]</code> 。

如果 <code>nums</code> 中存在 132 模式的子序列 ，返回 <code>true</code> ；否则，返回 <code>false</code> 。

 

示例 1：

<pre>
输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。
</pre>

示例 2：

<pre>
输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
</pre>

示例 3：

<pre>
输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
</pre>

 

提示：

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 <= n <= 2 * 105</code></li>
	<li><code>-109 <= nums[i] <= 109</code></li>
</ul>