苍溪建设局网站,wordpress启用特色,合肥seo优化外包公司,沈阳网站制作公司思路Every day a Leetcode
题目来源#xff1a;376. 摆动序列
解法1#xff1a;动态规划
约定#xff1a;
某个序列被称为「上升摆动序列」#xff0c;当且仅当该序列是摆动序列#xff0c;且最后一个元素呈上升趋势。某个序列被称为「下降摆动序列」#xff0c;当且仅当…Every day a Leetcode
题目来源376. 摆动序列
解法1动态规划
约定
某个序列被称为「上升摆动序列」当且仅当该序列是摆动序列且最后一个元素呈上升趋势。某个序列被称为「下降摆动序列」当且仅当该序列是摆动序列且最后一个元素呈下降趋势。特别地对于长度为 1 的序列它既是「上升摆动序列」也是「下降摆动序列」。序列中的某个元素被称为「峰」当且仅当该元素两侧的相邻元素均小于它。序列中的某个元素被称为「谷」当且仅当该元素两侧的相邻元素均大于它。特别地对于位于序列两端的元素只有一侧的相邻元素小于或大于它我们也称其为「峰」或「谷」。对于序列中既非「峰」也非「谷」的元素我们称其为「过渡元素」。
状态数组
up[i]表示以前 i 个元素中的某一个为结尾的最长的「上升摆动序列」的长度。down[i]表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。
最终的状态转移方程为 最终的答案即为 up[n−1] 和 down[n−1] 中的较大值其中 n 是序列的长度。
代码
/** lc appleetcode.cn id376 langcpp** [376] 摆动序列*/// lc codestart
class Solution
{
public:int wiggleMaxLength(vectorint nums){// 特判if (nums.size() 1)return nums.size();int n nums.size();// 状态数组// up[i]表示以前i个元素中的某一个为结尾的最长的「上升摆动序列」的长度vectorint up(n 1, 0);// down[i]表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度vectorint down(n 1, 0);// 初始化// 对于长度为1的序列它既是「上升摆动序列」也是「下降摆动序列」up[1] down[1] 1;// 状态转移for (int i 2; i n; i){if (nums[i - 1] nums[i - 2]){up[i] max(up[i - 1], down[i - 1] 1);down[i] down[i - 1];}else if (nums[i - 1] nums[i - 2]){up[i] up[i - 1];down[i] max(up[i - 1] 1, down[i - 1]);}else{up[i] up[i - 1];down[i] down[i - 1];}}return max(up[n], down[n]);}
};
// lc codeend结果 复杂度分析
时间复杂度O(n)其中 n 是序列的长度。我们只需要遍历该序列一次。
空间复杂度O(n)其中 n 是序列的长度。我们需要开辟两个长度为 n 的数组。
空间优化
代码
/** lc appleetcode.cn id376 langcpp** [376] 摆动序列*/// lc codestart// 动态规划// class Solution
// {
// public:
// int wiggleMaxLength(vectorint nums)
// {
// // 特判
// if (nums.size() 1)
// return nums.size();
// int n nums.size();
// // 状态数组
// // up[i]表示以前i个元素中的某一个为结尾的最长的「上升摆动序列」的长度
// vectorint up(n 1, 0);
// // down[i]表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度
// vectorint down(n 1, 0);
// // 初始化
// // 对于长度为1的序列它既是「上升摆动序列」也是「下降摆动序列」
// up[1] down[1] 1;
// // 状态转移
// for (int i 2; i n; i)
// {
// if (nums[i - 1] nums[i - 2])
// {
// up[i] max(up[i - 1], down[i - 1] 1);
// down[i] down[i - 1];
// }
// else if (nums[i - 1] nums[i - 2])
// {
// up[i] up[i - 1];
// down[i] max(up[i - 1] 1, down[i - 1]);
// }
// else
// {
// up[i] up[i - 1];
// down[i] down[i - 1];
// }
// }
// return max(up[n], down[n]);
// }
// };// 动态规划-空间优化class Solution
{
public:int wiggleMaxLength(vectorint nums){// 特判if (nums.size() 1)return nums.size();int n nums.size();int up 1, down 1;// 状态转移for (int i 1; i n; i){if (nums[i] nums[i - 1])up max(up, down 1);else if (nums[i] nums[i - 1])down max(down, up 1);}return max(up, down);}
};
// lc codeend结果 解法2贪心
观察这个序列可以发现我们不断地交错选择「峰」与「谷」可以使得该序列尽可能长。证明非常简单如果我们选择了一个「过渡元素」那么在原序列中这个「过渡元素」的两侧有一个「峰」和一个「谷」。不失一般性我们假设在原序列中的出现顺序为「峰」「过渡元素」「谷」。如果「过渡元素」在选择的序列中小于其两侧的元素那么「谷」一定没有在选择的序列中出现我们可以将「过渡元素」替换成「谷」同理如果「过渡元素」在选择的序列中大于其两侧的元素那么「峰」一定没有在选择的序列中出现我们可以将「过渡元素」替换成「峰」。这样一来我们总可以将任意满足要求的序列中的所有「过渡元素」替换成「峰」或「谷」。并且由于我们不断地交错选择「峰」与「谷」的方法就可以满足要求因此这种选择方法就一定可以达到可选元素数量的最大值。
这样我们只需要统计该序列中「峰」与「谷」的数量即可注意序列两端的数也是「峰」或「谷」但需要注意处理相邻的相同元素。
在实际代码中我们记录当前序列的上升下降趋势。每次加入一个新元素时用新的上升下降趋势与之前对比如果出现了「峰」或「谷」答案加一并更新当前序列的上升下降趋势。
代码
/** lc appleetcode.cn id376 langcpp** [376] 摆动序列*/// lc codestart// 动态规划// class Solution
// {
// public:
// int wiggleMaxLength(vectorint nums)
// {
// // 特判
// if (nums.size() 1)
// return nums.size();
// int n nums.size();
// // 状态数组
// // up[i]表示以前i个元素中的某一个为结尾的最长的「上升摆动序列」的长度
// vectorint up(n 1, 0);
// // down[i]表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度
// vectorint down(n 1, 0);
// // 初始化
// // 对于长度为1的序列它既是「上升摆动序列」也是「下降摆动序列」
// up[1] down[1] 1;
// // 状态转移
// for (int i 2; i n; i)
// {
// if (nums[i - 1] nums[i - 2])
// {
// up[i] max(up[i - 1], down[i - 1] 1);
// down[i] down[i - 1];
// }
// else if (nums[i - 1] nums[i - 2])
// {
// up[i] up[i - 1];
// down[i] max(up[i - 1] 1, down[i - 1]);
// }
// else
// {
// up[i] up[i - 1];
// down[i] down[i - 1];
// }
// }
// return max(up[n], down[n]);
// }
// };// 动态规划-空间优化// class Solution
// {
// public:
// int wiggleMaxLength(vectorint nums)
// {
// // 特判
// if (nums.size() 1)
// return nums.size();
// int n nums.size();
// int up 1, down 1;
// // 状态转移
// for (int i 1; i n; i)
// {
// if (nums[i] nums[i - 1])
// up max(up, down 1);
// else if (nums[i] nums[i - 1])
// down max(down, up 1);
// }
// return max(up, down);
// }
// };// 贪心class Solution
{
public:int wiggleMaxLength(vectorint nums){// 特判if (nums.size() 1)return nums.size();int n nums.size();int preDiff nums[1] - nums[0];int ans preDiff ! 0 ? 2 : 1;for (int i 2; i n; i){int diff nums[i] - nums[i - 1];if ((diff 0 preDiff 0) || (diff 0 preDiff 0)){ans;preDiff diff;}}return ans;}
};
// lc codeend结果 复杂度分析
时间复杂度O(n)其中 n 是序列的长度。我们只需要遍历该序列一次。
空间复杂度O(1)。我们只需要常数空间来存放若干变量。
第二种贪心思路统计变化次数
代码
// 贪心2class Solution
{
public:int wiggleMaxLength(vectorint nums){// 特判if (nums.size() 1)return nums.size();int n nums.size();int direction 0; //-1表示下降1表示上升int count 0; // 变化次数for (int i 1; i n; i){if (nums[i] nums[i - 1]){if (direction ! 1){direction 1;count;}}else if (nums[i] nums[i - 1]){if (direction ! -1){direction -1;count;}}}// 因为统计的是变化的次数最终的结果是序列的长度所以需要1return count 1;}
};结果 复杂度分析
时间复杂度O(n)其中 n 是序列的长度。我们只需要遍历该序列一次。
空间复杂度O(1)。我们只需要常数空间来存放若干变量。
