0456. 132 Pattern
https://leetcode.com/problems/132-pattern
Description
Given an array of n
integers nums
, a 132 pattern is a subsequence of three integers nums[i]
, nums[j]
and nums[k]
such that i < j < k
and nums[i] < nums[k] < nums[j]
.
Return true
if there is a 132 pattern in nums
, otherwise, return false
.
Example 1:
**Input:** nums = [1,2,3,4]
**Output:** false
**Explanation:** There is no 132 pattern in the sequence.
Example 2:
**Input:** nums = [3,1,4,2]
**Output:** true
**Explanation:** There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
**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].
Constraints:
n == nums.length
1 <= n <= 2 * 105
-109 <= nums[i] <= 109
ac1: Monotonic sequence
This is very tricky to be honest, hard to come up with.
class Solution {
public boolean find132pattern(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
int num2 = Integer.MIN_VALUE;
for (int i = nums.length - 1; i >= 0; i--) {
int num1 = nums[i];
if (num1 < num2) return true; // Found [num1, num3, num2]: "stack.peek()" -> num3, which always > num2.
// Decreasing stack.
while (!stack.isEmpty() && nums[i] > stack.peek()) {
num2 = stack.pop();
}
stack.push(nums[i]);
}
return false;
}
}
Last updated
Was this helpful?