LeetCode讲解篇之456. 132 模式
文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
这题需要我们尝试找到三个数，假设三个数的下标分别是i，j，k，需要满足条件：i < j < k && nums[i] < nums[k] < nums[j]
这类型的题目我们一般尝试使用控制变量法，针对这题我们可以将 j 和 k 控制住，用一个最大的 k 来表示，那么我们这题就转化为是否能找到三个数满足条件：i < maxK && nums[i] < nums[maxK]
对于maxK，我们可以使用单调栈求解
题解代码
func find132pattern(nums []int) bool {
n := len(nums)
// 从栈顶到栈底单调递增的单调栈
st := []int{nums[n - 1]}
maxK := math.MinInt
// 倒序遍历
for i := n - 2; i >= 0; i-- {
if nums[i] < maxK {
// 满足条件：i < maxK && nums[i] < nums[maxK]
return true
}
// 维护单调栈，并且尝试更新maxK
for len(st) > 0 && nums[i] > st[len(st) - 1] {
maxK = max(maxK, st[len(st) - 1])
st = st[:len(st) - 1]
}
st = append(st, nums[i])
}
// 不存在满足条件：i < maxK && nums[i] < nums[maxK] 的情况
return false
}
题目链接
https://leetcode.cn/problems/132-pattern/description/