泰安口碑好的网站建设腾讯wordpress 建站教程

泰安口碑好的网站建设,腾讯wordpress 建站教程,模板网站免费,投诉做单骗子网站哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题第二篇#xff01; 什么是“摆动”#xff1f;简单说就是一上一下。比如 [1, 7, 4, 9, 2, 5]#xff0c;差值是 6, -3, 5, -7, 3#xff0c;正负交替#xff0c;这就是摆动序列。 而 [1, 4, 7, 9] 单调递增#…哈喽各位我是前端小L。欢迎来到贪心算法专题第二篇 什么是“摆动”简单说就是一上一下。比如[1, 7, 4, 9, 2, 5]差值是6, -3, 5, -7, 3正负交替这就是摆动序列。 而[1, 4, 7, 9]单调递增或者[1, 1, 1]平的都不是摆动。我们的任务是给你一个数组你可以随意删除里面的元素也就是求子序列剩下的元素必须构成一个摆动序列。请问最长能剩多少个力扣 376. 摆动序列https://leetcode.cn/problems/wiggle-subsequence/题目分析输入整数数组nums。目标最长摆动子序列的长度。例子[1, 17, 5, 10, 13, 15, 10, 5, 16, 8]整个数组显然不是摆动的比如10, 13, 15连着涨。我们可以删掉13保留10, 15就变成了...10, 15, 10...一上一下。实际上我们只需要保留所有的“峰”和“谷”删掉所有在半山腰上的点。核心思维忽略“平坡”只数“峰谷”想象把你手里的数组画成一张折线图。摆动的本质就是折线的拐点。如果连续上升1 - 2 - 3 - 4这是一条直线上坡。为了构成摆动我们只需要保留起点1和终点4。中间的2和3都可以删掉因为它们没有改变趋势。贪心策略我们只需要统计数组中**“峰”Peak和“谷”Valley**的数量。峰数值先升后降。即preDiff 0且curDiff 0。谷数值先降后升。即preDiff 0且curDiff 0。平坡处理这是难点比如1 - 2 - 2 - 2 - 3。这种平坡应该被视为单调的一部分不计入摆动除非平坡之后方向变了。算法流程初始化curDiff当前数与后一个数的差值。preDiff前一对数的差值。result记录峰谷个数。默认序列最少有一个元素除非空数组所以初始为 1默认把最右边的那个端点算上。遍历数组从0到nums.size() - 2计算nums[i]和nums[i1]的差。判断拐点如果(preDiff 0 curDiff 0)—— 出现谷。或者(preDiff 0 curDiff 0)—— 出现峰。注意这里的是为了处理由平坡变成上下坡的情况如1-1-2中间的1算谷底。更新状态result。preDiff curDiff。关键点只有在出现摆动变化的时候才更新preDiff。这样可以自动过滤掉单调区间内的平坡。代码实现 (C)C#include vector using namespace std; class Solution { public: int wiggleMaxLength(vectorint nums) { if (nums.size() 1) return nums.size(); int curDiff 0; // 当前一对元素的差值 int preDiff 0; // 前一对元素的差值 int result 1; // 记录峰值个数默认最后一个元素算一个峰值 for (int i 0; i nums.size() - 1; i) { curDiff nums[i 1] - nums[i]; // 出现峰或谷 // preDiff 0 curDiff 0 : 之前是平或降现在升了谷 // preDiff 0 curDiff 0 : 之前是平或升现在降了峰 if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) { result; // 关键细节只在摆动变化的时候更新 preDiff // 这样能处理单调区间中有平坡的情况如 1-2-2-2-3 // preDiff 会一直保持为正直到遇到下降 preDiff curDiff; } } return result; } };深度复杂度分析时间复杂度O(N)我们只需要遍历一次数组。空间复杂度O(1)只需要几个变量记录差值和结果。相比之下动态规划解法通常需要两个数组up[N]和down[N]空间复杂度为O(N)虽然可以优化到 O(1)但逻辑比贪心复杂。总结贪心的“视觉化”今天这道题如果只看数字很容易被“平坡”、“删除元素”绕晕。 但如果把它想象成**“山脉图”**贪心策略就显而易见了我们只想要山顶和谷底山腰上的石头全扔掉这就是贪心算法的魅力——通过忽略中间过程单调区间直接抓住关键变化转折点。下一题预告 如果我们在一个数组中寻找**“和最大”的连续子数组**最大子序和贪心算法该如何操作 策略很简单如果当前的累加和变成了负数它对未来不仅没有贡献还是个累赘那我们就果断抛弃它从头开始算下期见