2026-08-05：比较双调部分的和。用go语言，给定一个整数数组，它的排列规律是先严格递增到达唯一的最高点，然后再严格递减。我们以这个最

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。

第三步：判断当前元素是否为峰值

• 如果同时满足以下三个条件，则认为当前元素是峰值：

1. 索引i大于 0（说明有前一个元素）；

2. 索引i + 1小于数组长度（说明有后一个元素，但代码中未显式检查，因为双调数组保证峰值不会出现在两端）；

3. 前一个元素的值小于当前值，且当前值大于后一个元素的值。

• 一旦检测到峰值，将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]的运行过程

• 初始diff=0,inc=true。

• i=0, x=1：非峰值，inc=true → diff += 1 → diff=1。

• i=1, x=3：前一个1<3且3>2，满足峰值条件 → inc=false，不操作diff。

• i=2, x=2：非峰值，inc=false → diff -= 2 → diff=-1。

• i=3, x=1：非峰值，inc=false → diff -= 1 → diff=-2。

• 最终 diff=-2 < 0，返回 1（递减部分更大），与预期一致。

复杂度分析

•时间复杂度：算法只需一次从左到右的遍历，访问每个元素常数次操作，因此总时间复杂度为O(n)，其中 n 为数组长度（n ≤ 100000，满足性能要求）。

•额外空间复杂度：除了输入数组本身外，只使用了几个固定变量（diff、inc、循环索引等），不随数组规模变化，因此额外空间复杂度为O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func compareBitonicSums(nums []int) int {
    diff := 0
    inc := true
    for i, x := range nums {
        if i > 0 && nums[i-1] < x && x > nums[i+1] {
            inc = false
            // 注意峰顶抵消掉了，不算入 diff
        } else if inc {
            diff += x
        } else {
            diff -= x
        }
    }

     if diff > 0 {
        return 0
    }
    if diff < 0 {
        return 1
    }
    return -1
}

 func main() {
    nums := []int{1, 3, 2, 1}
    result := compareBitonicSums(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def compare_bitonic_sums(nums: List[int]) -> int:
    diff = 0
    inc = True  # 当前是否处于递增阶段

     for i, x in enumerate(nums):
        # 检测峰值：前一个元素小于当前，且当前大于后一个元素
        if i > 0 and i + 1 < len(nums) and nums[i-1] < x and x > nums[i+1]:
            inc = False
            # 峰值不计入 diff（因为两边都包含，相互抵消）
        elif inc:
            diff += x
        else:
            diff -= x

     if diff > 0:
        return 0   # 递增部分（不含峰值）和大
    elif diff < 0:
        return 1   # 递减部分（不含峰值）和大
    else:
        return -1  # 两者相等

 # 测试用例
if __name__ == "__main__":
    nums = [1, 3, 2, 1]
    print(compare_bitonic_sums(nums)) 

C++完整代码如下：

  

  

using namespace std;

 int compareBitonicSums(const vector& nums) {
    int diff = 0;
    bool inc = true;  // 当前是否处于递增阶段

     for (size_t i = 0; i < nums.size(); ++i) {
        int x = nums[i];
        // 检测峰值：前一个元素小于当前，且当前大于后一个元素（同时确保索引不越界）
        if (i > 0 && i + 1 < nums.size() && nums[i-1] < x && x > nums[i+1]) {
            inc = false;
            // 峰值不计入 diff，因为两边都包含，相互抵消
        } else if (inc) {
            diff += x;
        } else {
            diff -= x;
        }
    }

     if (diff > 0) return 0;   // 递增部分（不含峰值）和大
    if (diff < 0) return 1;   // 递减部分（不含峰值）和大
    return -1;                // 两者相等
}

 int main() {
    vector nums = {1, 3, 2, 1};
    int result = compareBitonicSums(nums);
    cout << result << endl;
    return 0;
}

在这里插入图片描述