C++ | Leetcode C++题解之第456题132模式
题目:
题解:
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
vector<int> candidate_i = {nums[0]};
vector<int> candidate_j = {nums[0]};
for (int k = 1; k < n; ++k) {
auto it_i = upper_bound(candidate_i.begin(), candidate_i.end(), nums[k], greater<int>());
auto it_j = lower_bound(candidate_j.begin(), candidate_j.end(), nums[k], greater<int>());
if (it_i != candidate_i.end() && it_j != candidate_j.begin()) {
int idx_i = it_i - candidate_i.begin();
int idx_j = it_j - candidate_j.begin() - 1;
if (idx_i <= idx_j) {
return true;
}
}
if (nums[k] < candidate_i.back()) {
candidate_i.push_back(nums[k]);
candidate_j.push_back(nums[k]);
}
else if (nums[k] > candidate_j.back()) {
int last_i = candidate_i.back();
while (!candidate_j.empty() && nums[k] > candidate_j.back()) {
candidate_i.pop_back();
candidate_j.pop_back();
}
candidate_i.push_back(last_i);
candidate_j.push_back(nums[k]);
}
}
return false;
}
};
原文地址:https://blog.csdn.net/Ddddddd_158/article/details/142710278
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!