题目描述
给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成,并同时满足:i < j < k 和 nums[i] < nums[k] < nums[j] 。
如果 nums 中存在 132 模式的子序列 ,返回 true ;否则,返回 false 。
样例
输入:nums = [1,2,3,4]
输出:false
解释:序列中不存在 132 模式的子序列。
算法1
(暴力枚举) $O(n^3)$
显然不能通过测试
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
for(int k = j + 1; k < n; k++){
if(nums[i] < nums[j] && nums[i] < nums[j] && nums[k] < nums[j]){
return true;
}
}
}
}
return false;
}
};
算法2
优化,枚举ai
对于每个ai,后面是否存在满足如下要求的ak: ak>ai, 在ai,ak之间有aj,aj>ak
每次只要找最大的ak,然后判断是否大于ai,用单调栈
https://www.acwing.com/video/2650/
https://leetcode-cn.com/problems/132-pattern/solution/xiang-xin-ke-xue-xi-lie-xiang-jie-wei-he-95gt/
没搞懂,多看看
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
int right = INT_MIN;
stack<int> stk;
for(int i = n - 1; i >= 0; i--){
if(nums[i] < right) return true;
while(stk.size() && stk.top() < nums[i]){
right = max(right, stk.top());
stk.pop();
}
stk.push(nums[i]);
}
return false;
}
};