0456.132 Pattern

# 456. 132 Pattern#

## 题目 #

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

``````Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.
``````

Example 2:

``````Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
``````

Example 3:

``````Input: [-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].
``````

## 解题思路 #

• 这一题用暴力解法一定超时
• 这一题算是单调栈的经典解法，可以考虑从数组末尾开始往前扫，维护一个递减序列

## 代码 #

``````
package leetcode

import (
"fmt"
"math"
)

// 解法一 单调栈
func find132pattern(nums []int) bool {
if len(nums) < 3 {
return false
}
num3, stack := math.MinInt64, []int{}
for i := len(nums) - 1; i >= 0; i-- {
if nums[i] < num3 {
return true
}
for len(stack) != 0 && nums[i] > stack[len(stack)-1] {
num3 = stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
stack = append(stack, nums[i])
fmt.Printf("stack = %v \n", stack)
}
return false
}

// 解法二 暴力解法，超时！
func find132pattern1(nums []int) bool {
if len(nums) < 3 {
return false
}
for j := 0; j < len(nums); j++ {
stack := []int{}
for i := j; i < len(nums); i++ {
if len(stack) == 0 || (len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]]) {
stack = append(stack, i)
} else if nums[i] < nums[stack[len(stack)-1]] {
index := len(stack) - 1
for ; index >= 0; index-- {
if nums[stack[index]] < nums[i] {
return true
}
}
}
}
}
return false
}

``````

Sep 6, 2020