枚举专题.

=====模式=====

“132模式”——Leetcode 456. 132 模式

分析与思路：

class Solution {
public:bool find132pattern(vector<int>& nums) {int n = nums.size();if(n < 3)   return false;// 枚举最大的那个nums[j]（在中间的那个数）// ①维护一个左边的最小值int left_min = nums[0];multiset<int> right_all;// ②右边的元素维护成一个有序的集合（方便二分）for(int k = 2; k < n; k ++) right_all.insert(nums[k]);for(int j = 1; j < n - 1; j ++) // 0一定留给左边的元素, n-1一定留给k{if(nums[j] > left_min){auto it = right_all.upper_bound(left_min);if(it != right_all.end() && *it < nums[j]){return true;}}// 维护一下两个变量left_min = min(left_min, nums[j]);right_all.erase(right_all.find(nums[j + 1]));   // erase应该传入迭代器!!!}return false;}
};

“1324模式”——Leetcode 2552. 统计上升四元组

 

思路与132模式类似，通过维护一些信息来控制复杂度。（维护什么，如何维护是重点。）

总体思路：

维护细节：

class Solution {
public:     // 顺序(i, j, k, l)long long countQuadruplets(vector<int>& nums) {long long res = 0;int n = nums.size();// ①维护great[k][x]:即idx在k的右边, 且比x(=nums[j])大的元素个数vector<vector<int>> great(n, vector<int>(n + 1));   // 注意:数组内的元素都是<=n 的for(int k = n - 2; k >= 2; k --){   // 按照定义，至少要留一个第四位置给l,所以从n-2开始倒序枚举great[k] = great[k + 1];for(int x = 1; x < nums[k + 1]; x ++)great[k][x] ++;}// ②less[j][x]:即idx在j的左边,且x(=nums[k])小的元素个数// 这里可以简化为一维的, 随着j的更新而更新（第一维就是当前的j, 预处理出来直接用）vector<int> less(n + 1, 0);for(int j = 1; j < n - 2; j ++){for(int x = nums[j - 1]; x <= n; x ++)less[x] ++;for(int k = j + 1; k < n - 1; k ++)if(nums[j] > nums[k])res += (long long)less[nums[k]] * great[k][nums[j]];}return res;}
};