在线建站网页制作网站建设平台,wordpress 手机浏览器,专业外贸网站制作,怎么制作图片和视频一起的小视频个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
给你一个整数数组 nums 判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i j k 使得 nums[i] nums[j] nums[k] 返回 true 否则返回 false 。
示例一 输入nums [1,2,3,4,5] 输出true 解释任何 i j k 的三元组都满足题意 示例二 输入nums [5,4,3,2,1] 输出false 解释不存在满足题意的三元组 示例三 输入nums [2,1,5,0,4,6] 输出true 解释三元组 (3, 4, 5) 满足题意因为 nums[3] 0 nums[4] 4 nums[5] 6 注意
1 nums.length 5 * 105-231 nums[i] 231 - 1
2️⃣题目解析
解题思路 1.使用两个变量a和b来存储当前的最小值和次小值初始时将a设置为数组中的第一个元素将b设置为整型最大值。
2.遍历数组对于每个元素nums[i]判断它是否大于b。如果是说明找到了递增的三元组直接返回true。
3.如果nums[i]不大于b则判断是否大于a。如果是更新b为nums[i]以保证b始终是当前的次小值。
4.如果nums[i]既不大于b也不大于a则将a更新为nums[i]以保证a始终是当前的最小值。 如果遍历完整个数组都没有找到递增的三元组则返回false。
本题的贪心策略贪心的核心思想是尽量保持a和b的值最小以便有更大的机会找到递增的三元组。
3️⃣解题代码
class Solution {
public:bool increasingTriplet(vectorint nums) {int a nums[0];int b INT_MAX;for(int i 1;i nums.size();i){if(nums[i] b) return true;else if(nums[i] a) b nums[i];else a nums[i];}return false;}
};
