Dare2Solve
The wiggleMaxLength
problem requires us to find the length of the longest wiggle subsequence in an array. A wiggle sequence is defined as a series of numbers where the differences between successive numbers strictly alternate between positive and negative. The goal is to identify the maximum length of such a sequence from the input array nums
.
The idea is to track whether the difference between consecutive elements is increasing or decreasing. A "wiggle" happens when an increasing sequence is followed by a decreasing one, and vice versa. If we can count these "wiggles," we can derive the length of the longest wiggle subsequence.
dif
) between consecutive numbers, which helps determine whether the current number is part of a wiggle subsequence.O(n), where n
is the length of the input array. We traverse the array only once.
O(1), as we use only a few extra variables to store state and counters.
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.empty()) return 0;
int count = 1;
int dif = -1; // Initialize dif to -1 (undefined)
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (dif == 1 || dif == -1) {
dif = 0;
count++;
}
} else if (nums[i] < nums[i + 1]) {
if (dif == 0 || dif == -1) {
dif = 1;
count++;
}
}
}
return count;
}
};
class Solution:
def wiggleMaxLength(self, nums):
if not nums:
return 0
count = 1
dif = None # Use None to represent undefined
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
if dif == 1 or dif is None:
dif = 0
count += 1
elif nums[i] < nums[i + 1]:
if dif == 0 or dif is None:
dif = 1
count += 1
return count
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 0) return 0;
int count = 1;
Integer dif = null; // Use null to represent undefined
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (dif == null || dif == 1) {
dif = 0;
count++;
}
} else if (nums[i] < nums[i + 1]) {
if (dif == null || dif == 0) {
dif = 1;
count++;
}
}
}
return count;
}
}
var wiggleMaxLength = function (nums) {
let dif = undefined
let count = 1
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (dif == 1 || dif == undefined) {
dif = 0
count = count + 1
}
}
else if (nums[i] < nums[i + 1]) {
if ((dif == 0 || dif == undefined)) {
dif = 1
count = count + 1
}
}
} return count
};