个人评价：枚举遍历需要一定的策略，进阶优化如果不知道单调栈还真很难想到
题目难度：🌟 🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）
另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章
132 模式
题目描述
给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
**进阶：**很容易想到时间复杂度为 O(n^2) 的解决方案，你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？
示例 1：
输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。
示例 2：
输入：nums = [3,1,4,2]
输出：true
**解释：**序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
示例 3：
输入：nums = [-1,3,2,0]
输出：true
**解释：**序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
提示：
n == nums.length 1 <= n <= 104 -109 <= nums[i] <= 109
解题思路
方法一
枚举遍历，难点在于选择怎么遍历，以及怎么取数，思路如下：
从左向右，遍历寻找数「2」，存在前置数「 3」& 数「1」时停止
// 验证是否为数 「2」
func checkMax2(nums []int, index int) bool {
if index < 2 {
return false
}
max2 := nums[index]
max := max2
min := max2
maxIndex := 0
for i:=index; i>=0; i-- {
//fmt.Printf("index: %d\n", index)
if nums[i] > max {
max = nums[i]
maxIndex = i
}
if nums[i] < min && maxIndex > i { // 数「1」 不仅要比 数「2」小，且数「3」得在其之后
min = nums [i]
}
//fmt.Printf("i: %d, max: %d, min: %d\n", i, max, min)
if max > max2 && min < max2 {
return true
}
}
return false
}
func find132pattern(nums []int) bool {
for i := len(nums) -1; i > 1; i-- {
if checkMax2(nums, i) {
return true
}
}
return false
}
复杂度？
🙌 外层 O(n) 里层 O(n) => O(n²) 空间复杂度 O(1)
方法二
方法一相当于暴力破解，时间复杂度有点高，那么能否空间换时间？
这里，引入 「单调栈」 这一算法。
如果熟悉单调栈，应该就不难解，另找到个网友的精辟理解方式🐂🍺，如下：
设定两个变量，从右向左遍历
right 用于存储最右边的值，即 132 的 2
mid 用于存储中间和右边的待选项池子
这个待选项池子什么意思呢？
咱们首先由题目，确认两点：
- 最右边的值一定要小于中间的值
- 了让左边能找到小于右边的值，所以咱们要确保右边在小于中间的前提下，要尽可能的大
咱们可以把中间当作公司大领导，右边当成公司二领导，左边当成大领导的公子，池子当作公司拥有的公车库：
- 小领导的车一定不能比大领导的车高端或者新潮，不然不合规矩
- 大领导和二领导要么都配车，要么都不配车
- 来了新车如果领导都有车了，且新车比二领导的差，那就给大领导的公子，事情就成了！
- 来了新车如果比大领导的低端，二领导的高端，二领导先别急，大领导还没换，你换什么，等等吧
- 来了新车如果比大领导现有的高端，那么给大领导换车;大领导换车了高兴，把车库里仅次于大领导新车的车，直接换给二领导
经过上面的讲解，你是不是发现了，如果能找到值比right小，说明就成了
作者：bloodborne 力扣（LeetCode）链接
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处
func find132pattern(nums []int) bool {
l := len(nums)
if l <= 2 {
return false
}
var mid []int
right := math.MinInt32
for i := l - 1; i >= 0; i-- {
if nums[i] < right {
return true
}
for len(mid) != 0 && mid[len(mid)-1] <nums[i] {
right = mid[len(mid)-1] // 尽量给二领导配好车，前提是比大领导的差一点
mid = mid[:len(mid)-1] // 清出刚才的车
}
mid = append(mid, nums[i]) // 把最新的好车压入车库
}
return false
}
总结
数组暴力破解使用枚举的方式还真不少是从右向左较优
单调栈的使用，有一定的理解难度，有不少题也是用相关方式（如 接雨水 等）
对单调栈理解仍不熟练，等下次遇上类似题可总结一番