2026-08-05比较双调部分的和。用go语言给定一个整数数组它的排列规律是先严格递增到达唯一的最高点然后再严格递减。我们以这个最高点作为分界将数组划分为两个区域从数组开头到最高点含最高点为左侧区域从最高点到数组末尾含最高点为右侧区域。接着分别计算这两个区域内所有元素的总和并比较它们的大小。如果左侧区域的总和更大结果记为0如果右侧区域的总和更大结果记为1如果两边总和相等结果记为-1。特别需要注意的是最高点这个元素在两侧求和时都会被重复计入一次。3 n nums.length 100000。1 nums[i] 1000000000。nums 是一个双调数组。输入 nums [1,3,2,1]。输出 1。解释峰值元素是 nums[1] 3递增部分 [1, 3]和为 1 3 4递减部分 [3, 2, 1]和为 3 2 1 6因为递减部分的和更大返回 1。题目来自力扣3909。大体步骤如下第一步初始化变量设置一个整数变量diff初始值为 0它用于记录“递增部分不含峰值元素总和”与“递减部分不含峰值元素总和”的差值。设置一个布尔标志inc初始值为true表示当前遍历位置处于数组的递增阶段。第二步遍历数组从数组的第一个元素开始逐个访问每个元素同时获取它的索引i和值x。第三步判断当前元素是否为峰值如果同时满足以下三个条件则认为当前元素是峰值索引i大于 0说明有前一个元素索引i 1小于数组长度说明有后一个元素但代码中未显式检查因为双调数组保证峰值不会出现在两端前一个元素的值小于当前值且当前值大于后一个元素的值。一旦检测到峰值将inc设为false表示后续元素属于递减阶段。并且这个峰值元素本身不参与diff的累加或累减因为峰值在左右两侧都出现求和比较时彼此抵消不需要单独处理。第四步非峰值元素的分阶段累加如果当前元素不是峰值则根据inc的值决定如何处理若inc为true仍在递增阶段将当前元素的值加到diff中。若inc为false已进入递减阶段将当前元素的值减到diff中相当于从左侧总和中扣减右侧元素。第五步遍历完成后的结果判定遍历结束后diff的数值等于“递增部分不含峰值所有元素之和”减去“递减部分不含峰值所有元素之和”。由于峰值在两侧求和中都被计入一次两边的总和分别加上同一个峰值后它们的差值保持不变因此diff同时也等于“递增部分含峰值总和”减去“递减部分含峰值总和”。如果diff 0说明递增部分总和更大函数返回0。如果diff 0说明递减部分总和更大函数返回1。如果diff 0说明两部分总和相等函数返回-1。针对示例[1, 3, 2, 1]的运行过程初始diff0,inctrue。i0, x1非峰值inctrue → diff 1 → diff1。i1, x3前一个13且32满足峰值条件 → incfalse不操作diff。i2, x2非峰值incfalse → diff - 2 → diff-1。i3, x1非峰值incfalse → diff - 1 → diff-2。最终 diff-2 0返回 1递减部分更大与预期一致。复杂度分析时间复杂度算法只需一次从左到右的遍历访问每个元素常数次操作因此总时间复杂度为O(n)其中 n 为数组长度n ≤ 100000满足性能要求。额外空间复杂度除了输入数组本身外只使用了几个固定变量diff、inc、循环索引等不随数组规模变化因此额外空间复杂度为O(1)。Go完整代码如下packagemainimport(fmt)funccompareBitonicSums(nums[]int)int{diff:0inc:truefori,x:rangenums{ifi0nums[i-1]xxnums[i1]{incfalse// 注意峰顶抵消掉了不算入 diff}elseifinc{diffx}else{diff-x}}ifdiff0{return0}ifdiff0{return1}return-1}funcmain(){nums:[]int{1,3,2,1}result:compareBitonicSums(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListdefcompare_bitonic_sums(nums:List[int])-int:diff0incTrue# 当前是否处于递增阶段fori,xinenumerate(nums):# 检测峰值前一个元素小于当前且当前大于后一个元素ifi0andi1len(nums)andnums[i-1]xandxnums[i1]:incFalse# 峰值不计入 diff因为两边都包含相互抵消elifinc:diffxelse:diff-xifdiff0:return0# 递增部分不含峰值和大elifdiff0:return1# 递减部分不含峰值和大else:return-1# 两者相等# 测试用例if__name____main__:nums[1,3,2,1]print(compare_bitonic_sums(nums))C完整代码如下#includeiostream#includevectorusingnamespacestd;intcompareBitonicSums(constvectorintnums){intdiff0;boolinctrue;// 当前是否处于递增阶段for(size_t i0;inums.size();i){intxnums[i];// 检测峰值前一个元素小于当前且当前大于后一个元素同时确保索引不越界if(i0i1nums.size()nums[i-1]xxnums[i1]){incfalse;// 峰值不计入 diff因为两边都包含相互抵消}elseif(inc){diffx;}else{diff-x;}}if(diff0)return0;// 递增部分不含峰值和大if(diff0)return1;// 递减部分不含峰值和大return-1;// 两者相等}intmain(){vectorintnums{1,3,2,1};intresultcompareBitonicSums(nums);coutresultendl;return0;}
