LeetCode-376.-摆动序列-java题解
目录
LeetCode 376. 摆动序列 java题解
只要不满足摆动条件，就不更新count和prediff
当 prevDiff 取等号时，比如 prevDiff == 0，在这种情况下，如果 currDiff > 0，说明从持平状态转变为上升状态，这是一种有效的摆动起始情况；同理，如果 currDiff < 0，则是从持平状态转变为下降状态，也属于有效的摆动起始情况。例如序列 [1, 1, 2]，第一个 1 到第二个 1 时 prevDiff = 0，第二个 1 到 2 时 currDiff > 0，这种从持平到上升的情况应该被视为摆动的开始，所以需要包含 prevDiff == 0 的情况
从摆动子序列的定义角度：摆动子序列要求序列中的元素按照一定的规律交替出现上升和下降。当序列中只有一个元素时，它可以被看作是一个特殊的摆动子序列，虽然不存在真正意义上的上升或下降交替，但它本身可以作为摆动子序列的起始点或基础，具有唯一性和确定性，符合摆动子序列的最小单元概念，所以定义其摆动数为 1。
class Solution {
public int wiggleMaxLength(int[] nums) {
int len=nums.length;
if(len==1) return 1;
if(len==2){
return nums[0]==nums[1]?1:2;
}
int count=1;
int prediff=0;
int curdiff=0;
for(int i=1;i<len;i++){
curdiff=nums[i]-nums[i-1];
if(curdiff>0){
if(prediff<=0){
count++;
prediff=curdiff;
}
}
else if(curdiff<0){
if(prediff>=0){
count++;
prediff=curdiff;
}
}
else{
//平坡，跟上个数一样，不改变
}
}
return count;
}
}动态规划
// DP
class Solution {
public int wiggleMaxLength(int[] nums) {
// 0 i 作为波峰的最大长度
// 1 i 作为波谷的最大长度
int dp[][] = new int[nums.length][2];
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < nums.length; i++){
//i 自己可以成为波峰或者波谷
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j < i; j++){
if (nums[j] > nums[i]){
// i 是波谷
dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
}
if (nums[j] < nums[i]){
// i 是波峰
dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
}
}
}
return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
}很容易可以发现，对于我们当前考虑的这个数，要么是作为山峰（即 nums[i] > nums[i-1]），要么是作为山谷（即 nums[i] < nums[i - 1]）。
设 dp 状态dp[i][0]，表示考虑前 i 个数，第 i 个数作为山峰的摆动子序列的最长长度 设 dp 状态dp[i][1]，表示考虑前
i 个数，第 i 个数作为山谷的摆动子序列的最长长度 则转移方程为：
dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] <
nums[i]，表示将 nums[i]接到前面某个山谷后面，作为山峰。 dp[i][1] = max(dp[i][1], dp[j][0]
- 1)，其中0 < j < i且nums[j] > nums[i]，表示将 nums[i]接到前面某个山峰后面，作为山谷。 初始状态：