大家好呀今天来聊一个超实用的算法题给你一个整数数组代表海拔高度怎么只保留那些“关键点”——也就是第一个点、最后一个点以及所有趋势发生改变的点从上升变下降或从下降变上升比如输入[6, 4, 2, -2, 5, 3, 2, 2, -1, -1, 4]输出[6, -2, 5, -1, 4]看我们只保留了起始点6、谷底-2、峰顶5、谷底-1、终点4。中间那些连续上升或下降的部分都被优雅地忽略啦再比如输入[6, 10, 11, 13]输出[6, 13]因为全程只升不降所以只保留首尾。输入[1, 1]输出[1]两个相等只保留一个。核心思路遍历 转折点检测O(n) 时间O(1) 额外空间思路超级简单先把第一个元素加入结果数组。从第二个元素遍历到倒数第二个元素对每个位置判断它是不是“峰”或“谷”峰当前元素 上一个已加入的元素且 下一个元素谷当前元素 上一个已加入的元素且 下一个元素如果是峰或谷就加入结果。最后检查结果数组的最后一个元素是否等于原数组最后一个元素如果不相等再把最后一个元素加进去。注意连续的相等元素会被忽略因为比较时用的是严格大于/小于。代码实现多语言版C#includeiostream#includevectorusingnamespacestd;vectorintextractPoints(vectorintarr){intnarr.size();vectorintans;if(n0)returnans;ans.push_back(arr[0]);for(inti1;in-1;i){if(arr[i]ans.back()arr[i]arr[i1]){ans.push_back(arr[i]);}elseif(ans.back()arr[i]arr[i]arr[i1]){ans.push_back(arr[i]);}}if(ans.back()!arr[n-1]){ans.push_back(arr[n-1]);}returnans;}intmain(){vectorintarr{6,4,2,-2,5,3,2,2,-1,-1,4};vectorintresultextractPoints(arr);for(intx:result)coutx ;return0;}最近刷题时总被“转折点”这类数组问题卡住把算法跑成“黑盒”可太难受了。强烈安利一个神器——图码它用60种交互式动画可视化把数据结构彻底拆解清楚。无论是输入自定义数据生成动画还是上传C/C/Java/Python代码进行可视化解析都能让你一眼看透算法逻辑。特别适合备战408考研和数据结构期末考试的宝子7*24小时AI还能随时解释代码。别犹豫了快去体验一下图码-数据结构与算法交互式可视化平台访问网站https://totuma.cnJavaimportjava.util.ArrayList;classGfG{publicstaticArrayListIntegerextractPoints(int[]arr){intnarr.length;ArrayListIntegeransnewArrayList();if(n0)returnans;ans.add(arr[0]);for(inti1;in-1;i){if(arr[i]ans.get(ans.size()-1)arr[i]arr[i1]){ans.add(arr[i]);}elseif(ans.get(ans.size()-1)arr[i]arr[i]arr[i1]){ans.add(arr[i]);}}if(ans.get(ans.size()-1)!arr[n-1]){ans.add(arr[n-1]);}returnans;}publicstaticvoidmain(String[]args){int[]arr{6,4,2,-2,5,3,2,2,-1,-1,4};ArrayListIntegerresultextractPoints(arr);for(intval:result)System.out.print(val );}}PythondefextractPoints(arr):nlen(arr)result[]ifn0:returnresult result.append(arr[0])foriinrange(1,n-1):ifarr[i]result[-1]andarr[i]arr[i1]:result.append(arr[i])elifresult[-1]arr[i]andarr[i]arr[i1]:result.append(arr[i])ifresult[-1]!arr[-1]:result.append(arr[-1])returnresultif__name____main__:arr[6,4,2,-2,5,3,2,2,-1,-1,4]print(*extractPoints(arr))JavaScriptfunctionextractPoints(arr){constnarr.length;constresult[];if(n0)returnresult;result.push(arr[0]);for(leti1;in-1;i){if(arr[i]result[result.length-1]arr[i]arr[i1]){result.push(arr[i]);}elseif(result[result.length-1]arr[i]arr[i]arr[i1]){result.push(arr[i]);}}if(result[result.length-1]!arr[n-1]){result.push(arr[n-1]);}returnresult;}constarr[6,4,2,-2,5,3,2,2,-1,-1,4];constresultextractPoints(arr);console.log(...result);运行结果6 -2 5 -1 4✅总结这个算法的时间复杂度是 O(n)空间复杂度 O(1)不算输出数组的话。它巧妙地利用了“上一个已加入的元素”作为参考避免了复杂的趋势状态维护超级简洁适合用在数据压缩、路径简化、股票趋势关键点提取等场景。快去试试吧记得关注我解锁更多算法小技巧
✨ 算法小技巧：如何优雅地提取数组中的“转折点”？
大家好呀今天来聊一个超实用的算法题给你一个整数数组代表海拔高度怎么只保留那些“关键点”——也就是第一个点、最后一个点以及所有趋势发生改变的点从上升变下降或从下降变上升比如输入[6, 4, 2, -2, 5, 3, 2, 2, -1, -1, 4]输出[6, -2, 5, -1, 4]看我们只保留了起始点6、谷底-2、峰顶5、谷底-1、终点4。中间那些连续上升或下降的部分都被优雅地忽略啦再比如输入[6, 10, 11, 13]输出[6, 13]因为全程只升不降所以只保留首尾。输入[1, 1]输出[1]两个相等只保留一个。核心思路遍历 转折点检测O(n) 时间O(1) 额外空间思路超级简单先把第一个元素加入结果数组。从第二个元素遍历到倒数第二个元素对每个位置判断它是不是“峰”或“谷”峰当前元素 上一个已加入的元素且 下一个元素谷当前元素 上一个已加入的元素且 下一个元素如果是峰或谷就加入结果。最后检查结果数组的最后一个元素是否等于原数组最后一个元素如果不相等再把最后一个元素加进去。注意连续的相等元素会被忽略因为比较时用的是严格大于/小于。代码实现多语言版C#includeiostream#includevectorusingnamespacestd;vectorintextractPoints(vectorintarr){intnarr.size();vectorintans;if(n0)returnans;ans.push_back(arr[0]);for(inti1;in-1;i){if(arr[i]ans.back()arr[i]arr[i1]){ans.push_back(arr[i]);}elseif(ans.back()arr[i]arr[i]arr[i1]){ans.push_back(arr[i]);}}if(ans.back()!arr[n-1]){ans.push_back(arr[n-1]);}returnans;}intmain(){vectorintarr{6,4,2,-2,5,3,2,2,-1,-1,4};vectorintresultextractPoints(arr);for(intx:result)coutx ;return0;}最近刷题时总被“转折点”这类数组问题卡住把算法跑成“黑盒”可太难受了。强烈安利一个神器——图码它用60种交互式动画可视化把数据结构彻底拆解清楚。无论是输入自定义数据生成动画还是上传C/C/Java/Python代码进行可视化解析都能让你一眼看透算法逻辑。特别适合备战408考研和数据结构期末考试的宝子7*24小时AI还能随时解释代码。别犹豫了快去体验一下图码-数据结构与算法交互式可视化平台访问网站https://totuma.cnJavaimportjava.util.ArrayList;classGfG{publicstaticArrayListIntegerextractPoints(int[]arr){intnarr.length;ArrayListIntegeransnewArrayList();if(n0)returnans;ans.add(arr[0]);for(inti1;in-1;i){if(arr[i]ans.get(ans.size()-1)arr[i]arr[i1]){ans.add(arr[i]);}elseif(ans.get(ans.size()-1)arr[i]arr[i]arr[i1]){ans.add(arr[i]);}}if(ans.get(ans.size()-1)!arr[n-1]){ans.add(arr[n-1]);}returnans;}publicstaticvoidmain(String[]args){int[]arr{6,4,2,-2,5,3,2,2,-1,-1,4};ArrayListIntegerresultextractPoints(arr);for(intval:result)System.out.print(val );}}PythondefextractPoints(arr):nlen(arr)result[]ifn0:returnresult result.append(arr[0])foriinrange(1,n-1):ifarr[i]result[-1]andarr[i]arr[i1]:result.append(arr[i])elifresult[-1]arr[i]andarr[i]arr[i1]:result.append(arr[i])ifresult[-1]!arr[-1]:result.append(arr[-1])returnresultif__name____main__:arr[6,4,2,-2,5,3,2,2,-1,-1,4]print(*extractPoints(arr))JavaScriptfunctionextractPoints(arr){constnarr.length;constresult[];if(n0)returnresult;result.push(arr[0]);for(leti1;in-1;i){if(arr[i]result[result.length-1]arr[i]arr[i1]){result.push(arr[i]);}elseif(result[result.length-1]arr[i]arr[i]arr[i1]){result.push(arr[i]);}}if(result[result.length-1]!arr[n-1]){result.push(arr[n-1]);}returnresult;}constarr[6,4,2,-2,5,3,2,2,-1,-1,4];constresultextractPoints(arr);console.log(...result);运行结果6 -2 5 -1 4✅总结这个算法的时间复杂度是 O(n)空间复杂度 O(1)不算输出数组的话。它巧妙地利用了“上一个已加入的元素”作为参考避免了复杂的趋势状态维护超级简洁适合用在数据压缩、路径简化、股票趋势关键点提取等场景。快去试试吧记得关注我解锁更多算法小技巧
