做ps网页设计的网站有哪些,wordpress个人介绍主题,公司网址怎么注册,申请网站多少钱1. 题目
给定一个未排序的数组#xff0c;判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i j k ≤ n-1#xff0c; 使得 arr[i] arr[j] arr[k] #xff0c;返回 true ; 否则返回 false 。 说…1. 题目
给定一个未排序的数组判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i j k ≤ n-1 使得 arr[i] arr[j] arr[k] 返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n)空间复杂度为 O(1) 。
示例 1:输入: [1,2,3,4,5]
输出: true
示例 2:输入: [5,4,3,2,1]
输出: false来源力扣LeetCode 链接https://leetcode-cn.com/problems/increasing-triplet-subsequence 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
left 记录最小值right 记录次小值更新 left right如果 num 大于 right则找到
class Solution {
public:bool increasingTriplet(vectorint nums) {int left INT_MAX;int right INT_MAX; for (int i 0; i nums.size();i) {if (nums[i] left)left nums[i];else if (nums[i] right) right nums[i];elsereturn true;} return false;}
};正向扫描获取到当前位置最小值下标 dpmin反向扫描获取当前位置到最后的最大值下标 dpmax遍历数组dpmin[i]idpmax[i]dpmin[i] i dpmax[i]dpmin[i]idpmax[i], 则满足
class Solution {
public:bool increasingTriplet(vectorint nums) {if(nums.size() 3)return false;int dpmin[nums.size()], dpmax[nums.size()], temp;temp INT_MAX;for(int i 0; i nums.size(); i)if(nums[i] temp){dpmin[i] i;temp nums[i];}elsedpmin[i] dpmin[i-1];temp INT_MIN;for(int i nums.size()-1; i 0; --i)if(nums[i] temp){dpmax[i] i;temp nums[i];}elsedpmax[i] dpmax[i1];for(int i 0; i nums.size(); i)if(i dpmin[i] i dpmax[i])return true;return false;}
};
