算法沉淀——贪心算法二
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] 表示长度为 i+1 的递增子序列中,最后一个元素的最小值。在遍历数组过程中,不断更新这个数组,以确保它仍然满足递增的性质。
每当新元素加入时,可以利用二分查找找到当前元素在 ret 数组中的插入位置,然后更新这个位置上的值。这样,就能够在数组中维护递增子序列的信息。
这种方法的关键点在于,我们只关心递增子序列的最后一个元素,而不是整个递增子序列的具体形状。通过维护最后一个元素的最小值,可以在遍历数组时保持递增子序列的长度信息,并在需要时更新。
代码
class Solution {
public:
int lengthOfLIS(vector
int n=nums.size();
vector
ret.push_back(nums[0]);
for(int i=1;i if(nums[i]>ret.back()) ret.push_back(nums[i]); else{ int left=0,right=ret.size()-1; while(left { int mid=(left+right)>>1; if(ret[mid] else right=mid; } 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(vector int n=nums.size(); int a=nums[0],b=INT_MAX; for(int i=1;i if(nums[i]>b) return true; else if(nums[i]>a) b=nums[i]; else a=nums[i]; } return false; } }; 03.最长连续递增序列 题目链接:https://leetcode.cn/problems/longest-continuous-increasing-subsequence/ 给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l < 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(vector int ret=0,n=nums.size(); for(int i=0;i int j=i+1; while(j ret=max(ret,j-i); i=j; } 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(vector int ret=0,n=prices.size(); for(int i=0,prevMin=INT_MAX;i ret=max(ret,prices[i]-prevMin); prevMin=min(prevMin,prices[i]); } return ret; } }; 精彩文章
发表评论