宁波网站关键词排名推广,wordpress简码插件,前端和后端哪个常熬夜,什么学历可以进中建376.摆动序列
376. 摆动序列
中等
如果连续数字之间的差严格地在正数和负数之间交替#xff0c;则数字序列称为 摆动序列 。第一个差#xff08;如果存在的话#xff09;可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如#xff0c; [1, 7…376.摆动序列
376. 摆动序列
中等
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如 [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) 。示例 3
输入nums [1,2,3,4,5,6,7,8,9]
输出2提示
1 nums.length 10000 nums[i] 1000 进阶你能否用 O(n) 时间复杂度完成此题?
class Solution { // 定义一个公共方法wiggleMaxLength接收一个整数数组nums作为参数返回摆动长度 public int wiggleMaxLength(int[] nums) { // 如果数组长度小于等于1则摆动长度等于数组长度 if (nums.length 1) { return nums.length; } // 当前差值初始化为0 // 表示当前元素与前一个元素的差值 int curDiff 0; // 上一个差值初始化为0 // 表示前一个元素与前一个元素的差值 // 在第一次循环时preDiff实际上是一个“初始值”用于比较 int preDiff 0; // 摆动长度初始化为1 // 因为至少有一个元素所以摆动长度至少为1 int count 1; // 从数组的第二个元素开始遍历 for (int i 1; i nums.length; i) { // 计算当前差值 curDiff nums[i] - nums[i - 1]; // 判断当前差值与上一个差值的符号是否相反 // 如果相反说明摆动长度增加 // 注意curDiff 0 preDiff 0 表示当前差值为正且上一个差值为负或零 // curDiff 0 preDiff 0 表示当前差值为负且上一个差值为正或零 if ((curDiff 0 preDiff 0) || (curDiff 0 preDiff 0)) { count; // 摆动长度增加 preDiff curDiff; // 更新上一个差值为当前差值 } } // 返回摆动长度 return count; }
} 要求删除元素使其达到最大摆动序列应该删除什么元素呢 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。
整体最优整个序列有最多的局部峰值从而达到最长摆动序列。
实际操作上其实连删除的操作都不用做因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了
在计算是否有峰值的时候大家知道遍历的下标 i 计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]如果prediff 0 curdiff 0 或者 prediff 0 curdiff 0 此时就有波动就需要统计。
这是我们思考本题的一个大题思路但本题要考虑三种情况
情况一上下坡中有平坡情况二数组首尾两端情况三单调坡中有平坡
情况一上下坡中有平坡
例如 [1,2,2,2,1]这样的数组如图 它的摇摆序列长度是多少呢 其实是长度是 3也就是我们在删除的时候 要不删除左面的三个 2要不就删除右边的三个 2。
如图可以统一规则删除左边的三个 2 在图中当 i 指向第一个 2 的时候prediff 0 curdiff 0 当 i 指向最后一个 2 的时候 prediff 0 curdiff 0。
如果我们采用删左面三个 2 的规则那么 当 prediff 0 curdiff 0 也要记录一个峰值因为他是把之前相同的元素都删掉留下的峰值。
所以我们记录峰值的条件应该是 (preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)为什么这里允许 prediff 0 就是为了 上面我说的这种情况。
情况二数组首尾两端
所以本题统计峰值的时候数组最左面和最右面如何统计呢
题目中说了如果只有两个不同的元素那摆动序列也是 2。
例如序列[2,5]如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
因为我们在计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]的时候至少需要三个数字才能计算而数组只有两个数字。
不写死的话如何和我们的判断规则结合在一起呢
可以假设数组最前面还有一个数字那这个数字应该是什么呢 那么为了规则统一针对序列[2,5]可以假设为[2,2,5]这样它就有坡度了即 preDiff 0即将preDif初始化为0如图 针对以上情形result 初始为 1默认最左面有一个峰值此时 curDiff 0 preDiff 0那么 result计算了左面的峰值最后得到的 result 就是 2峰值个数为 2 即摆动序列长度为 2
情况三单调坡度有平坡
在版本一中我们忽略了一种情况即 如果在一个单调坡度上有平坡例如[1,2,2,2,3,4]如图 图中我们可以看出版本一的代码在三个地方记录峰值但其实结果因为是 2因为 单调中的平坡 不能算峰值即摆动。
之所以版本一会出问题是因为我们实时更新了 prediff。
那么我们应该什么时候更新 prediff 呢
我们只需要在 这个坡度 摆动变化的时候更新 prediff 就行这样 prediff 在 单调区间有平坡的时候 就不会发生变化造成我们的误判。 738.单调递增的数字
738. 单调递增的数字
中等
提示
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。 示例 1:
输入: n 10
输出: 9示例 2:
输入: n 1234
输出: 1234示例 3:
输入: n 332
输出: 299提示:
0 n 109
思路是在原来给出的数字中处理从后向前遍历如果遇到前一个数大于后一个数的情况就将该前一个数减1将后面的数字都改为9这样既保持了递增又使得最后的结果最大
class Solution { public int monotoneIncreasingDigits(int n) { // 将整数n转换为字符串 String s String.valueOf(n); // 将字符串转换为字符数组方便进行字符操作 char[] sChar s.toCharArray(); // 初始化start为数组长度表示还没有找到需要修改的位置 int start sChar.length; // 从数组倒数第二个字符开始向前遍历 for(int i sChar.length - 2; i 0; i--){ // 如果当前字符大于下一个字符说明不满足单调递增的条件 if(sChar[i] sChar[i 1]){ // 更新start为当前位置1表示从当前位置开始后面的字符都需要变为9 start i 1; // 将当前字符减1以便让后续字符满足单调递增的条件 sChar[i] - 1; } } // 从start位置开始将后面的所有字符都变为9以满足单调递增的条件 for(int i start; i sChar.length; i){ sChar[i] 9; } // 将修改后的字符数组转换回整数 int num Integer.parseInt(String.valueOf(sChar)); // 返回修改后的整数 return num; }
}
题目要求小于等于N的最大单调递增的整数那么拿一个两位的数字来举例。
例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]--然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。
这一点如果想清楚了这道题就好办了。
此时是从前向后遍历还是从后向前遍历呢
从前向后遍历的话遇到strNum[i - 1] strNum[i]的情况让strNum[i - 1]减一但此时如果strNum[i - 1]减一了可能又小于strNum[i - 2]。
这么说有点抽象举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。
那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299
确定了遍历顺序之后那么此时局部最优就可以推出全局找不出反例试试贪心。
