文章

10

粉丝

66

获赞

3

访问

42.0k

头像
题解:贪心算法
P897 上海交通大学2021年机试题
发布于2022年5月22日 12:30
阅读数 4.5k

对于下标范围 [l,r] 的连续子序列,如果对任意 l≤i<r 都满足 nums[i]<nums[i+1],则该连续子序列是递增序列。

假设数组 nums 的长度是 n,对于 0<l≤r<n−1,如果下标范围 [l,r] 的连续子序列是递增序列,则考虑 nums[l−1] 和nums[r+1]。

如果 nums[l−1]<nums[l],则将 nums[l−1] 加到 nums[l] 的前面,可以得到更长的连续递增序列.

如果 nums[r+1]>nums[r],则将 nums[r+1] 加到 nums[r] 的后面,可以得到更长的连续递增序列。

基于上述分析可知,为了得到最长连续递增序列,可以使用贪心的策略得到尽可能长的连续递增序列。做法是使用记录当前连续递增序列的开始下标和结束下标,遍历数组的过程中每次比较相邻元素,根据相邻元素的大小关系决定是否需要更新连续递增序列的开始下标。

具体而言,令 start 表示连续递增序列的开始下标,初始时 start=0,然后遍历数组 nums,进行如下操作。

如果下标 i>0 且 nums[i]≤nums[i−1],则说明当前元素小于或等于上一个元素,因此 nums[i−1] 和nums[i] 不可能属于同一个连续递增序列,必须从下标 i 处开始一个新的连续递增序列,因此令start=i。如果下标 i=0 或 nums[i]>nums[i−1],则不更新 start 的值。

此时下标范围 [start,i] 的连续子序列是递增序列,其长度为i−start+1,使用当前连续递增序列的长度更新最长连续递增序列的长度。

遍历结束之后,即可得到整个数组的最长连续递增序列的长度。

 

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans...
登录查看完整内容


登录后发布评论

1 条评论
snake
2022年5月25日 11:48

学习了

赞(0)