题目
132 模式
给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意：n 的值小于15000。
示例:
输入: [1, 2, 3, 4]
输出: False
解释: 序列中不存在132模式的子序列。
输入: [3, 1, 4, 2]
输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
输入: [-1, 3, 2, 0]
输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
提示:
n == nums.length1 <= n <= 104-109 <= nums[i] <= 109
解答
暴力循环解法的时间复杂度为 O(n^3) , 提交时将会超时，所以需要找到最少的时间复杂度算法，可以使用栈来保存一些结果，同时提前计算最小值
栈
- 用
mindp保存数组nums从0 ~ i的最小值 - 从
nums尾部开始循环，并且在循环过程中用栈保存一些信息，记作stack - 如果栈顶元素小于最小值，则一直pop出栈，同时要避免栈为空的情况
- 如果栈顶元素小于当前
nums数组值，则返回true - 最后返回
false
给个官方的解答图，可能看上去更好理解
image
func find132pattern(nums []int) bool {
if len(nums) < 3 {
return false
}
mindp := make([]int, len(nums))
mindp[0] = nums[0]
for i := 1; i < len(nums); i++ {
if mindp[i-1] < nums[i] {
mindp[i] = mindp[i-1]
}else {
mindp[i] = nums[i]
}
}
stack := make([]int, 0)
for i := len(nums)-1; i >= 0; i-- {
for len(stack) != 0 && stack[len(stack)-1] <= mindp[i] {
stack = stack[:len(stack)-1]
}
if len(stack) != 0 && stack[len(stack)-1] < nums[i] {
return true
}
stack = append(stack, nums[i])
}
return false
}
