一、解题思路

采用双指针法，就像切割字符串一样，来处理这个序列。 首先定义一对前后指针left和right，分别表示本递增区间的起始位置和终止位置 然后定义一个slnStart，来确定当前最优解（当前找到的最长递增序列）的起始位置 定义一个maxLength，其含义为当前找到的最长长度，设置初始值为1，意思是即使向量全逆序，也至少要输出一个元素 然后呢，挨个扫描向量的元素，查看下一个元素是不是递增的，直到找到本递增区间的终止位置 然后，根据得到的left和right值，就可以确定这个递增区间的长度，位right - left + 1，即使向量为全逆序，那么这个值也为1 根据当前找到的这个递增区间的长度和找到的最优解的长度maxLength比对，如果当前找到的这个递增区间的长度right - left + 1更长，就要更新maxLength和slnStart 然后输出即可

二、性能分析

只遍历了向量一次，所以时间复杂度为$O(n)$ 同时只设置了固定个变量，所以空间复杂度为$S(1)$

三、解题代码

#include <iostream> #include <vector> using namespace std; void sln(const vector<int>& vec){ auto len = vec.size(); auto left = 0; auto right = 0; int cur; int maxLength = 1; int slnStart = 0; for(; left < len; left++){ cur = vec[left]; for(right = left; right + 1 < len && vec[right + 1] > cur; right++){ cur = vec[right + 1]; } if(right - left + 1 > maxLength){ maxLength = right - left + 1; slnStart = left; } left = right; } for(int i = slnStart; i < slnStart + maxLength - 1; i++) cout << vec[i] << ' '; cout << vec.at(slnStart + maxLength - 1) << endl; } int main(){ int n; cin >> n; vector<int> vec(n, 0); for(int i = 0; i < n; i++) cin >> vec[i]; sln(vec); return 0; }

四、运行结果