題目

給定一個整數序列：a1, a2, ..., an，一個132模式的子序列 ai, aj, ak 被定義為：

當 i < j < k 時，ai < ak < aj。

設計一個演算法，當給定有 n 個數字的序列時，驗證這個序列中是否含有132模式的子序列。

注意：n 的值小於15000。

示例1:輸入: [1, 2, 3, 4] 輸出: False

解釋: 序列中不存在132模式的子序列。

示例 2:輸入: [3, 1, 4, 2]輸出: True

解釋: 序列中有 1 個132模式的子序列： [1, 4, 2].

示例 3:輸入: [-1, 3, 2, 0] 輸出: True

解釋: 序列中有 3 個132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

1、棧輔助；時間複雜度O(n)，空間複雜度O(n)

func find132pattern(nums []int) bool {	if len(nums) < 3 {		return false	}	minArr := make([]int, len(nums)) // minArr[i]是[0,i]中的最小值	minArr[0] = nums[0]	for i := 1; i < len(nums); i++ {		minArr[i] = min(nums[i], minArr[i-1])	}	stack := make([]int, 0)	for j := len(nums) - 1; j >= 0; j-- {		// a[i]<a[k]<a[j] => min[j]<a[k]<a[j]		if nums[j] > minArr[j] {			for len(stack) > 0 && stack[len(stack)-1] <= minArr[j] {				stack = stack[:len(stack)-1]			}			if len(stack) > 0 && stack[len(stack)-1] < nums[j] {				return true			}			stack = append(stack, nums[j])		}	}	return false}func min(a, b int) int {	if a > b {		return b	}	return a}

2、遍歷；時間複雜度O(n^2)，空間複雜度O(n)

func find132pattern(nums []int) bool {	if len(nums) < 3 {		return false	}	minArr := make([]int, len(nums)) // minArr[i]是[0,i]中的最小值	minArr[0] = nums[0]	for i := 1; i < len(nums); i++ {		minArr[i] = min(nums[i], minArr[i-1])	}	for j := len(nums) - 2; j >= 0; j-- {		if nums[j] != minArr[j] {			for k := j + 1; k < len(nums); k++ {				if nums[k] > minArr[j] && nums[k] < nums[j] {					return true				}			}		}	}	return false}func min(a, b int) int {	if a > b {		return b	}	return a}

3、棧輔助；時間複雜度O(n)，空間複雜度O(n)

func find132pattern(nums []int) bool {	if len(nums) < 3 {		return false	}	stack := make([]int, 0)	maxValue := math.MinInt32	for i := len(nums) - 1; i >= 0; i-- {		// i < k		if nums[i] < maxValue {			return true		}		for len(stack) > 0 && nums[i] > stack[len(stack)-1] {			last := len(stack) - 1			maxValue = max(maxValue, stack[last])			stack = stack[:last]		}		stack = append(stack, nums[i])	}	return false}func max(a, b int) int {	if a > b {		return a	}	return b}

Medium題目，單調棧應用