【leetcode】376. 摆动序列
题目内容
思路分析
方法一：贪心
贪心策略：只选极值点，而忽略中间的所有点。
可以贪的原因：只选极值点，可以增大后续元素被选中为摆动序列的概率。详见参考资料2和3中的图。
实际实现时，只需记录极值点的个数。可以按照参考资料1，默认最右端有一个极值点，最左端（-1下标处）有一个与下标0处元素一样的点。设当前差值为cur_diff，上次差值为pre_diff，则当(cur_diff > 0 && pre_diff <= 0) || (cur_diff < 0 && pre_diff >= 0)时，证明当前遍历点的左边出现了极值点，极值点个数+1。
方法二：动态规划
看到这个题目的第一感觉是用动态规划，可惜我没想出来...
官方的题解里有动态规划，但是写的很复杂，不想看了
代码
#include <vector>
#include <math.h>
#include <limits.h>
using namespace std;
// 贪心
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return n;
int peak_num = 1;
int pre_diff = 0;
for (int i = 1; i < n; ++i) {
int cur_diff = nums[i] - nums[i - 1];
if ((cur_diff > 0 && pre_diff <= 0) ||
(cur_diff < 0 && pre_diff >= 0)) {
++peak_num;
// 这个一定要放在if里面，否则会通不过一个很长的测试用例
// TODO：为什么？
pre_diff = cur_diff;
}
}
return peak_num;
}
};
int main() {
Solution s;
vector<int> input{ 1,17,5,10,13,15,10,5,16,8 };
int result = s.wiggleMaxLength(input);
int a = 0;
}
收获
- 好难好难好难