AlgoPressAppearance
0456-132模式
https://leetcode.cn/problems/132-pattern
给你一个整数数组 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 * 10^5
- -10^9 <= nums[i] <= 10^9
思路 【暴力，超时】
暴力法，3层循环
参考代码
csharp
public class Solution {
public bool Find132pattern(int[] nums) {
for(int i=0; i<nums.Length - 2; i++){
for(int j=i+1; j<nums.Length - 1; j++){
for (int k=j+1; k<nums.Length; k++){
if(nums[i] < nums[k] && nums[k] < nums[j] ){
return true;
}
}
}
}
return false;
}
}
缓存最小值 i, 遍历数组，逐步取最小值 minValue ，最后还是会超时，但是会少1层循环
参考代码
csharp
public class Solution{
public bool Find132pattern(int[] nums){
int minValue = nums[0];
for(int i=1; i<nums.Length - 1; i++){
for(int j=i+1; j<nums.Length; j++){
if(nums[i] > nums[j] && nums[j] > minValue){
return true;
}
}
minValue = Math.Min(minValue,nums[i]);
}
return false;
}
}
思路3【官方：单调栈】
思路：将最后一个数入栈
从后往前循环，发现 nums[i] 有大于后面栈内的数，就出栈，并且将出栈的数字，设置为132 中 2 那个数， 这样
csharp
public class Solution{
public bool Find132pattern(int[] nums){
int n = nums.Length;
Stack<int> candidateK = new Stack<int>();
candidateK.push(nums[n-1]);
int maxK = int.MinValue;
for(int i=n-2; i>=0; i--){
if(nums[i] < maxK){
return true;
}
while(candidateK.Count > 0 && nums[i] > candidateK.Peek()){
maxK = candidateK.Pop();
}
if(nums[i] > maxK){
candidateK.Push(nums[i]);
}
}
return false;
}
}
复习：20220520
csharp
public class Solution {
public bool Find132pattern(int[] nums) {
//从后往前寻找132中的2那个数，使用单调栈
int n = nums.Length;
Stack<int> stack = new Stack<int>();
int num2 = int.MinValue;
stack.Push(nums[n-1]);
for(int i=n-2; i>=0; i--){
if(nums[i] < num2){
return true;
}
while(stack.Count > 0 && nums[i] > stack.Peek()){ //找到第三个数
num2 = stack.Pop(); //将它设置为 num2 , 此时 3,2 都找到，剩下找到 nums[i] < num2 就满足了条件
}
if(nums[i] > num2){ //大于 num2 的入栈才有意义
stack.Push(nums[i]);
}
}
return false;
}
}