当前位置:网站首页>leetcode:334. 递增的三元子序列
leetcode:334. 递增的三元子序列
2022-08-10 10:09:00 【OceanStar的学习笔记】
题目来源
题目描述
题目解析
本质是问最长递增子序列长度能否超过2而已
一次遍历
因为我们需要求解的长度仅仅为3,所以我们可以直接将这个三元子序列的值记录下来;
使用两个指针m1和m2,初始化为INT_MAX,然后遍历数组:
- 如果m1 >= curr,则令m1 = curr
- 如果m1 < curr && m2 >= curr,则令m2 = curr
一旦m2被更新了,说明一定会有一个数小于m2,也就是我们成功组成了一个长度为2的递增子序列。所以我们一旦遍历到比m2还大的数,我们直接返回ture。
如果我们遇到比m1小的数,还是要更新m1,有可能的话也要更新m2为更小的值,毕竟m2的值越小,能组成长度为3的递增序列的可能性越大
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int m1 = INT32_MAX, m2 =INT32_MAX;
for(auto a : nums){
if(m1 >= a){
m1 = a;
}else if(m2 >= a){
m2 = a;
}else{
return true;
}
}
return false;
}
};
暴力超时
class Solution {
bool process(vector<int>& nums, int idx, std::vector<int>&path){
if(idx == nums.size()){
return path.size() >= 3;
}
bool p1 = process(nums, idx + 1, path);
bool p2 = false;
if(path.empty() || path.back() < nums[idx] ){
path.emplace_back(nums[idx]);
p2 = process(nums, idx + 1, path);
path.pop_back();
}
return p1 || p2;
}
public:
bool increasingTriplet(vector<int>& nums) {
std::vector<int>path;
return process(nums, 0, path);
}
};
类似题目
边栏推荐
猜你喜欢
Tencent releases the second-generation version of the quadruped robot Max, which completes jumps and somersaults on the plum blossom pile
[Azure Cloud] What is the difference between a service endpoint and a private link?point of view (1)
bus事件总线 使用
「时序数据库」使用cassandra进行时间序列数据扫描
「首席工程师」首席(Principal )工程师修炼之道
【知识论概念】《理由论的进展》鲁汶大学2022最新220页博士论文
WebView2 通过 PuppeteerSharp 实现爬取 王者 壁纸 (案例版)
裸辞→自我放松→闭关→复习→斩获Offer
LCD DRM驱动框架分析一
"Data Strategy" Results-Driven Enterprise Data Strategy: Organization and Governance
随机推荐
「业务架构」TOGAF建模:业务功能分解图
Which is the strongest workflow engine for "Technology Selection"?Chief Architecture Helps You Pick
俄罗斯宣布临时禁止进口摩尔多瓦植物产品
ESP8266 Tutorial 2 - Burn AT Firmware
「业务架构」TAGAF建模:业务服务/信息图
The Generation of Matlab Symbolic Functions and the Calculation of Its Function Values
Message Queuing Overview
dedecms supports one-click upload of Word content
「数据战略」结果驱动的企业数据策略:组织和治理
文本选中圆角样式border-radius
Taro小程序跨端开发入门实战
LeetCode Algorithm 1403. 非递增顺序的最小子序列
解决ASP.NET Core在Task中使用IServiceProvider的问题
[C language] Floating point number rounding
WebView2 通过 PuppeteerSharp 实现爬取 王者 壁纸 (案例版)
ELK框架搭建[通俗易懂]
[Azure Cloud] What is the difference between a service endpoint and a private link?point of view (1)
定时任务Quartz
网络安全笔记6——数字证书与公钥基础设施
[Internet of Things Architecture] The most suitable open source database for the Internet of Things