Week13 - 376. Wiggle Subsequence
Week13 - 376. Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:
Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2
Follow up:
Can you do it in O(n) time?
Credits:
Special thanks to @agave and @StefanPochmann for adding this problem and creating all test cases.
my solution:
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int size = nums.size();
if (size == 0) {
return 0;
}
vector<int> up(size, 0);
vector<int> down(size, 0);
up[0] = 1;
down[0] = 1;
for(int i=1; i<size; ++i){
if (nums[i] > nums[i-1]) {
up[i] = down[i-1] + 1;
down[i] = down[i-1];
}
else if (nums[i] < nums[i-1]) {
down[i] = up[i-1] + 1;
up[i] = up[i-1];
}
else {
up[i] = up[i-1];
down[i] = down[i-1];
}
}
return max(up[size-1], down[size-1]);
}
};
最新文章
- IOS竖屏应用单个页面横屏的解决办法
- myBatis批量查询操作,xml中使用foreach案例
- WINDOWS和Linux上安装php7 alpha 并安装 yaf
- div布局
- GET与POST在什么情况下使用
- Java连接各类数据库
- 金额的计算BigDecimal类
- redis入门(03)redis的配置
- 【一天一道LeetCode】#18. 4Sum
- Windows 7 下使用 pandoc 转换文档格式
- 【MM系列】SAP MB1A MB1B MB1C MB11 MIGO的区别解析
- 你真的知道什么是【共享Session】,什么是【单点登录】吗?
- nginx做代理离线下载插件
- MAC如何生成SSH key与GitHub关联
- TensorFlow入门
- POJ训练计划2528_Mayor&;#39;s posters(线段树/成段更新+离散化)
- vue 组件 模板中根数据绑定需要指明路径并通信父
- [CF1051F]The Shortest Statement (LCA+最短路)(给定一张n个点m条有权边的无向联通图,q次询问两点间的最短路)
- c++ json字符串转换成map管理
- [LeetCode][Java] Subsets
热门文章
- 公用flex类
- vue : 无法加载文件 C:\Users\XXX\AppData\Roaming\npm\vue.ps1,因为在此系统上禁止运行脚本
- Python 通过RSA实现license验证设备指纹与有效期
- 2014-04-27 南江滨大道 6KM 晴
- background的水平条纹和斜向条纹
- Django中使用djangorestframework产生Token
- 013-linux系统管理——系统资源查看
- Codeforces 961 容斥叉积判共线 树状数组递增思想题
- GUI学习之二十二——QRubberBand学习总结
- 安装了vs2019 编译node-sass node-gyp 找不到编译器的解决方法