使用kotlin解决这个问题:456. 132 模式 中等 758 相关企业 给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成,并同时满足:i < j < k 和 nums[i] < nums[k] < nums[j] 。 如果 nums 中存在 132 模式的子序列 ,返回 true ;否则,返回 false 。 示例 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 <= 2 * 105 -109 <= nums[i] <= 109
时间: 2024-02-02 18:03:44 浏览: 164
可以使用栈来解决这个问题,具体思路如下:
1. 遍历数组,对于每个元素 nums[i],找到它左边最小的元素 minLeft 和右边最大的元素 maxRight。
2. 如果 minLeft 和 maxRight 都存在且满足 minLeft < maxRight,则说明找到了 132 模式,返回 true。
3. 如果 nums[i] < maxRight,则把 (minLeft, maxRight) 加入到栈中。
4. 如果 nums[i] >= maxRight,则把栈中所有元素出栈,直到找到一个元素满足它的左边最小元素小于 maxRight,也就是找到了一个可能的 132 模式。如果栈为空,则说明当前元素不能作为 2,继续遍历。
5. 判断栈中是否存在满足 minLeft < maxRight 的元素,如果存在,则说明找到了 132 模式,返回 true。
6. 如果遍历完数组还没有返回 true,则说明不存在 132 模式,返回 false。
具体的 Kotlin 代码实现如下:
```kotlin
fun find132pattern(nums: IntArray): Boolean {
val stack = Stack<Pair<Int, Int>>()
var minLeft = nums[0]
for (i in 1 until nums.size) {
val num = nums[i]
while (stack.isNotEmpty() && stack.peek().second <= num) {
val pair = stack.pop()
if (pair.first < num) return true
}
if (num > minLeft) {
while (stack.isNotEmpty() && stack.peek().first >= minLeft) {
val pair = stack.pop()
if (pair.second < num) return true
minLeft = pair.first
}
stack.push(minLeft to num)
} else {
minLeft = num
}
}
return false
}
```
其中,Pair 的第一个元素表示 minLeft,第二个元素表示 maxRight。
阅读全文