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 <= 3 * 104
• -109 <= nums[i] <= 109

Solution(javascript)

// /** TODO O(N^2)
//  * @param {number[]} nums
//  * @return {boolean}
//  */
// const find132pattern = function (nums) {
//   const candidates = []
//   let stack = [] // 这里其实是一个区间，用来保存尽可能大的范围
//   for (const num of nums) {
//     if (
//       (num < stack[stack.length - 1] && num > stack[stack.length - 2])
//       || candidates.some(([a, b]) => a < num && num < b)
//     ) {
//       return true
//     } if (stack.length === 0) {
//       stack.push(num)
//     } else if (num >= stack[stack.length - 1]) {
//       while (stack.length >= 2) {
//         stack.pop()
//       }
//       stack.push(num)
//     } else if (num < stack[0]) {
//       candidates.push(stack)
//       stack = [num]
//     }
//   }
//   return false
// }

/** O(n)
 * @param {number[]} nums
 * @return {boolean}
 */
const find132pattern = function (nums) {
  let max = -Infinity
  const stack = []
  for (let i = nums.length - 1; i >= 0; i--) {
    while (nums[i] > stack[stack.length - 1]) {
      max = stack.pop()
    }
    if (nums[i] < max) {
      return true
    }
    stack.push(nums[i])
  }
  return false
}