建站公司经营,wordpress如何进入后台,二建报考报名入口,百度游戏排行榜风云榜算法沉淀——贪心算法二 01.最长递增子序列02.递增的三元子序列03.最长连续递增序列04.买卖股票的最佳时机 01.最长递增子序列
题目链接#xff1a;https://leetcode.cn/problems/longest-increasing-subsequence/
给你一个整数数组 nums #xff0c;找到其中最长严格递增子… 算法沉淀——贪心算法二 01.最长递增子序列02.递增的三元子序列03.最长连续递增序列04.买卖股票的最佳时机 01.最长递增子序列
题目链接https://leetcode.cn/problems/longest-increasing-subsequence/
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1
输入nums [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例 2
输入nums [0,1,0,3,2,3]
输出4示例 3
输入nums [7,7,7,7,7,7,7]
输出1提示
1 nums.length 2500-104 nums[i] 104
思路
可以通过维护一个数组其中 ret[i] 表示长度为 i1 的递增子序列中最后一个元素的最小值。在遍历数组过程中不断更新这个数组以确保它仍然满足递增的性质。
每当新元素加入时可以利用二分查找找到当前元素在 ret 数组中的插入位置然后更新这个位置上的值。这样就能够在数组中维护递增子序列的信息。
这种方法的关键点在于我们只关心递增子序列的最后一个元素而不是整个递增子序列的具体形状。通过维护最后一个元素的最小值可以在遍历数组时保持递增子序列的长度信息并在需要时更新。
代码
class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();vectorint ret;ret.push_back(nums[0]);for(int i1;in;i){if(nums[i]ret.back()) ret.push_back(nums[i]);else{int left0,rightret.size()-1;while(leftright){int mid(leftright)1;if(ret[mid]nums[i]) leftmid1;else rightmid;}ret[left]nums[i];}}return ret.size();}
};02.递增的三元子序列
题目链接https://leetcode.cn/problems/increasing-triplet-subsequence/
给你一个整数数组 nums 判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i j k 使得 nums[i] nums[j] nums[k] 返回 true 否则返回 false 。
示例 1
输入nums [1,2,3,4,5]
输出true
解释任何 i j k 的三元组都满足题意示例 2
输入nums [5,4,3,2,1]
输出false
解释不存在满足题意的三元组示例 3
输入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
思路
上一题的精简版可以直接用上面的代码返回长度是否大于等于三即可但在这里我们不需要这么复杂仅需连个变量即可。
代码
class Solution {
public:bool increasingTriplet(vectorint nums) {int nnums.size();int anums[0],bINT_MAX;for(int i1;in;i){if(nums[i]b) return true;else if(nums[i]a) bnums[i];else anums[i];}return false;}
};03.最长连续递增序列
题目链接https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1
输入nums [1,3,5,4,7]
输出3
解释最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的因为 5 和 7 在原数组里被 4 隔开。 示例 2
输入nums [2,2,2,2,2]
输出1
解释最长连续递增序列是 [2], 长度为1。 提示
1 nums.length 104-109 nums[i] 109
思路
当找到以某个位置为起点的最长连续递增序列后可以直接将下一个位置作为新的起点继续寻找下一个最长连续递增序列。
代码
class Solution {
public:int findLengthOfLCIS(vectorint nums) {int ret0,nnums.size();for(int i0;in;){int ji1;while(jnnums[j]nums[j-1]) j;retmax(ret,j-i);ij;}return ret;}
};04.买卖股票的最佳时机
题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1
输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。示例 2
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 没有交易完成, 所以最大利润为 0。提示
1 prices.length 1050 prices[i] 104
思路
遍历数组在每个位置 i 处计算当前价格与之前最低价格的差值更新最大利润。在遍历过程中始终保持记录前面最低价格的变量。当找到更低的价格时更新这个变量当计算当前位置的利润时与之前记录的最大利润进行比较如果更大则更新最大利润。
代码
class Solution {
public:int maxProfit(vectorint prices) {int ret0,nprices.size();for(int i0,prevMinINT_MAX;in;i){retmax(ret,prices[i]-prevMin);prevMinmin(prevMin,prices[i]);}return ret;}
};
