如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
- 相反，
[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
|
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
|
C++
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if(n == 1) return 1;
vector<int> up(n, 0);
vector<int> down(n, 0);
up[0] = 1;
down[0] = 1;
if(nums[1] - nums[0] > 0 ) up[1] = 2;
else if (nums[0] - nums[1] > 0) down[1] = 2;
else up[1] = down[1] = 1;
for(int i = 2; i < n; i ++){
if(nums[i]- nums[i - 1] > 0)
up[i] = max(down[i - 1] + 1, up[i - 1]);
else if(nums[i]- nums[i - 1] < 0)
down[i] = max(up[i - 1] + 1, down[i - 1]);
else {
down[i] = down[i -1];
up[i] = up[i - 1];
}
}
return max(up[n - 1], down[n - 1]);
}
};
|
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2) return n;
int prevdiff = nums[1] - nums[0];
int ret = prevdiff != 0 ? 2 : 1;
for (int i = 2; i < n; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
ret++;
prevdiff = diff;
}
}
return ret;
}
};
|
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
示例 2:
示例 3:
提示:
C++
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string str = to_string(n);
int len = str.size();
if(len == 1) return n;
for(int i = len - 1; i >0; i --) {
if(str[i - 1] > str[i]) {
str[i - 1] --;
for(int j = i; j < len; j ++) {
str[j] = '9';
}
}
}
return stoi(str);
}
};
|
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
|
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
|
提示：
n == ratings.length1 <= n <= 2 * 1040 <= ratings[i] <= 2 * 104
C++
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
if(n == 1) return 1;
vector<int> res(n);
for(int i = 1; i < n;i ++){
if((ratings[i] > ratings[i - 1]) && (res[i] <= res[i - 1]))
res[i] = res[i - 1] + 1;
else if((ratings[i - 1] > ratings[i]) && (res[i -1] <= res[i]))
res[i - 1] = res[i] + 1;
}
for(int i = n - 1; i >= 1;i --){
if((ratings[i] > ratings[i - 1]) && (res[i] <= res[i - 1]))
res[i] = res[i - 1] + 1;
else if((ratings[i - 1] > ratings[i]) && (res[i -1] <= res[i]))
res[i - 1] = res[i] + 1;
}
int sum = 0;
for(int e: res) sum += e;
return sum + n ;
}
};
|
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1：
输入：people =
输出：
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 是重新构造后的队列。
|
示例 2：
提示：
1 <= people.length <= 20000 <= hi <= 1060 <= ki < people.length- 题目数据确保队列可以被重建
C++
先对 [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 进行排序：
第一维度高的在前，第二维度低的在前，每次插入到第二维度下标所在处：[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
插入的过程：
插入[7,0]：[[7,0]]
插入[7,1]：[[7,0],[7,1]]
插入[6,1]：[[7,0],[6,1],[7,1]]
插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
class Solution {
public:
static bool cmp(const vector<int> a, const vector<int> b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
vector<vector<int>> res;
for(auto e: people) {
res.insert(res.begin() + e[1], e);
}
return res;
}
};
|