个人练习-Leetcode-978. Longest Turbulent Subarray
题目链接：https://leetcode.cn/problems/longest-turbulent-subarray/
题目大意：给出一个数列arr[]，求其最长的波浪子列长度。波浪子列的定义是：
- 在
arr[]中连续 - 每三个元素中，前两元素的增减性和后两元素增减性相反。这里的增减性是严格的。
思路：将原数组转化为【增减性数组】做，即
isUp[i]==true表示arr[i]
但问题是：可能存在相邻两个元素相等，即arr[i]==arr[i+1]，这时候有点烦，因为增减性的要求是严格的，要考虑一些边界情况（如arr[]所有元素相等）。那么就先把原数组拆分成一系列【相邻元素不相等的】子列，再按上面思路做就好了。
vector<vector<int>> inst;int pos = 0;for (int i = 1; i < arr.size(); i++) {if (arr[i] == arr[i-1]) {vector<int> tmp(arr.begin()+pos, arr.begin()+i);inst.push_back(tmp);pos = i;}}vector<int> tmp(arr.begin()+pos, arr.end());inst.push_back(tmp);
随后对每个【相邻元素不相等的】子列，遍历一遍来得到最长的满足要求的子列。注意一下长度小于等于2时候的处理。
int getLen(vector<int>& arr) {if (arr.size() <= 2)return arr.size();vector<bool> isUp(arr.size()-1, false);for (int i = 0; i < arr.size()-1; i++) {if (arr[i] < arr[i+1])isUp[i] = true;}int max_l = 1;int tmp_l = 1;for (int i = 1; i < isUp.size(); i++) {if (isUp[i-1] != isUp[i]) {tmp_l++;max_l = max(max_l, tmp_l);}else {tmp_l = 1;}}return max_l+1;}
完整代码
class Solution {
public:int getLen(vector<int>& arr) {if (arr.size() <= 2)return arr.size();vector<bool> isUp(arr.size()-1, false);for (int i = 0; i < arr.size()-1; i++) {if (arr[i] < arr[i+1])isUp[i] = true;}int max_l = 1;int tmp_l = 1;for (int i = 1; i < isUp.size(); i++) {if (isUp[i-1] != isUp[i]) {tmp_l++;max_l = max(max_l, tmp_l);}else {tmp_l = 1;}}return max_l+1;}int maxTurbulenceSize(vector<int>& arr) {vector<vector<int>> inst;int pos = 0;for (int i = 1; i < arr.size(); i++) {if (arr[i] == arr[i-1]) {vector<int> tmp(arr.begin()+pos, arr.begin()+i);inst.push_back(tmp);pos = i;}}vector<int> tmp(arr.begin()+pos, arr.end());inst.push_back(tmp);int max_len = 0;for (int i = 0; i < inst.size(); i++) {int tmp_len = getLen(inst[i]);max_len = max(max_len, tmp_len);}return max_len;}
};
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！