2026-05-10：找到带限制序列的最大值。用go语言，给定一个整数 n、一个二维整数数组 restrictions、以及一个长度为 n-1 的数组 diff。你需要生成一个长度为 n 的非负整数序

2026-05-10：找到带限制序列的最大值。用go语言，给定一个整数 n、一个二维整数数组 restrictions、以及一个长度为 n-1 的数组 diff。你需要生成一个长度为 n 的非负整数序列 a[0…n-1]，使得：

• a[0] 固定为 0。

• 对于每个 i（0 ≤ i ≤ n-2），相邻项差的绝对值不超过给定限制：|a[i] - a[i+1]| ≤ diff[i]。

• 对于 restrictions 中的每一项 [idx, maxVal]，都要保证对应位置满足：a[idx] ≤ maxVal。

在所有满足上述条件的序列中，你的目标是让序列里的“最大元素值”尽可能大。最终输出这个最大元素值的最优结果。

2 <= n <= 100000。

1 <= restrictions.length <= n - 1。

restrictions[i].length == 2。

restrictions[i] = [idx, maxVal]。

1 <= idx < n。

1 <= maxVal <= 1000000。

diff.length == n - 1。

1 <= diff[i] <= 10。

restrictions[i][0] 的值是唯一的。

输入: n = 10, restrictions = [[3,1],[8,1]], diff = [2,2,3,1,4,5,1,1,2]。

输出: 6。

解释:

序列 a = [0, 2, 4, 1, 2, 6, 2, 1, 1, 3] 满足给定的限制条件（a[3] <= 1 且 a[8] <= 1）。

序列中的最大值为 6。

题目来自力扣3796。

详细步骤

我会完全脱离代码，用纯文字、分步骤把整个解题过程讲清楚，同时最后给出时间和空间复杂度。

一、先明确题目核心规则

我们要构造一个长度为n的序列a，满足：

1. 起点固定：a[0] = 0
2. 相邻约束：|a[i] - a[i+1]| ≤ diff[i]（相邻两个数的差值绝对值不能超过对应diff值）
3. 点位约束：指定下标idx的值必须 ≤ 给定的maxVal
4. 目标：在所有合法序列中，让整个序列的最大值尽可能大，求这个最大可能值

二、整体解题思路（核心：两次遍历 + 约束融合）

整个算法的核心逻辑是：
先从左到右推导出每个位置能达到的理论最大值，再从右到左修正所有违反相邻约束和点位约束的值，最终得到合法的最优序列，再取最大值。

下面是分步骤详细过程：

步骤1：初始化所有位置的「硬上限」

1. 给序列的每一个位置0~n-1都设置一个初始最大允许值，默认是无穷大（表示暂时没有限制）。
2. 遍历所有的restrictions点位约束：
   • 把对应下标的硬上限直接修改为题目给定的maxVal。
   • 比如约束[3,1]，就把位置3的硬上限设为1；[8,1]就把位置8的硬上限设为1。
   • 其他没有约束的位置，上限保持无穷大。

这一步的作用：先把所有固定的点位限制记下来，后续推导不能超过这些值。

步骤2：从左到右遍历，计算「左向最大可能值」

从起点a[0]=0开始，向右依次计算每个位置能达到的最大理论值：

1. 起点固定：a[0] = 0
2. 对于第i+1个位置：
   • 它的理论最大值= 左边位置i的值 + 相邻允许的最大增量diff[i]
   • 同时不能超过该位置的硬上限（步骤1设置的值）
   • 最终取两者中的较小值作为当前位置的左向最大值

这一步的逻辑：只能向右走，每次最多加diff[i]，同时不能碰点位限制。
这一步结束后，得到的序列满足：

• 从左到右的相邻约束
• 所有点位硬上限约束
• 但不满足从右到左的相邻约束（右边的值可能太大，导致和左边的差值超标）

步骤3：从右到左遍历，修正序列为「完全合法值」

从最后一个位置开始，向左依次修正每个位置的值，让序列同时满足左右双向的相邻约束：

1. 从倒数第二个位置开始，向左遍历到第1个位置
2. 对于当前位置i：
   • 它的最大合法值= 右边位置i+1的值 + 相邻允许的最大增量diff[i]
   • 同时不能超过步骤2算出的左向最大值
   • 最终取两者中的较小值作为当前位置的最终值

这一步的作用：修正左到右推导时，右侧值过大导致的左侧不合法问题，让整个序列同时满足：

• 起点固定
• 所有相邻双向约束
• 所有点位约束
• 且序列中的每个值都是当前约束下能取到的最大值（保证整体最大值最优）

步骤4：计算最终结果

遍历修正后的完整序列，找出其中的最大值，就是题目要求的答案。

三、用题目示例验证过程（直观理解）

输入：

• n=10，序列长度10
• 约束：[3,1]、[8,1]
• diff = [2,2,3,1,4,5,1,1,2]

步骤1：设置硬上限

位置：0 1 2 3 4 5 6 7 8 9
上限：∞ ∞ ∞ 1 ∞ ∞ ∞ ∞ 1 ∞

步骤2：左→右推导（取最大理论值）

• a[0] = 0
• a[1] = min(0+2, ∞) = 2
• a[2] = min(2+2, ∞) = 4
• a[3] = min(4+3, 1) = 1（受约束限制）
• a[4] = min(1+1, ∞) = 2
• a[5] = min(2+4, ∞) = 6
• a[6] = min(6+5, ∞) = 11
• a[7] = min(11+1, ∞) = 12
• a[8] = min(12+1, 1) = 1（受约束限制）
• a[9] = min(1+2, ∞) = 3

左→右结果：[0,2,4,1,2,6,11,12,1,3]
（这个序列不合法：比如12和1的差值远超diff限制）

步骤3：右→左修正（得到合法序列）

从右往左依次修正，让相邻差值合规：
最终得到合法最优序列：[0,2,4,1,2,6,2,1,1,3]
（和题目解释的序列完全一致）

步骤4：取最大值

序列最大值 = 6 → 就是答案。

四、时间复杂度 & 额外空间复杂度

1. 总时间复杂度

整个过程只涉及三次线性遍历：

1. 初始化上限数组：O(n)
2. 左→右遍历：O(n)
3. 右→左遍历：O(n)
4. 求序列最大值：O(n)

所有操作都是和序列长度n成正比的线性操作，没有嵌套循环。
✅总时间复杂度：O(n)

2. 总额外空间复杂度

我们额外开辟了两个数组：

1. 存储每个位置硬上限的数组：长度n
2. 存储最终序列的数组：长度n

其他变量都是常数级空间，不随n变化。
✅总额外空间复杂度：O(n)

总结

1. 解题分四步：初始化点位上限 → 左向右推最大理论值 → 右向左修正合规值 → 取序列最大值；
2. 核心是通过两次遍历同时满足所有约束，并让序列最大值最优；
3. 时间复杂度：O(n)（线性效率，适合n≤10万的大数据量）；
4. 额外空间复杂度：O(n)（用两个长度为n的辅助数组完成计算）。

Go完整代码如下：

packagemainimport("fmt""math""slices")funcfindMaxVal(nint,restrictions[][]int,diff[]int)int{maxVal:=make([]int,n)fori:=rangemaxVal{maxVal[i]=math.MaxInt}for_,r:=rangerestrictions{maxVal[r[0]]=r[1]}a:=make([]int,n)fori,d:=rangediff{a[i+1]=min(a[i]+d,maxVal[i+1])}fori:=n-2;i>0;i--{a[i]=min(a[i],a[i+1]+diff[i])}returnslices.Max(a)}funcmain(){n:=10restrictions:=[][]int{{3,1},{8,1}}diff:=[]int{2,2,3,1,4,5,1,1,2}result:=findMaxVal(n,restrictions,diff)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-importmathdeffind_max_val(n,restrictions,diff):max_val=[math.inf]*nforrinrestrictions:max_val[r[0]]=r[1]a=[0]*nfori,dinenumerate(diff):a[i+1]=min(a[i]+d,max_val[i+1])foriinrange(n-2,0,-1):a[i]=min(a[i],a[i+1]+diff[i])returnmax(a)if__name__=="__main__":n=10restrictions=[[3,1],[8,1]]diff=[2,2,3,1,4,5,1,1,2]result=find_max_val(n,restrictions,diff)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<climits>usingnamespacestd;intfindMaxVal(intn,vector<vector<int>>&restrictions,vector<int>&diff){vector<int>maxVal(n,INT_MAX);for(auto&r:restrictions){maxVal[r[0]]=r[1];}vector<int>a(n,0);for(inti=0;i<diff.size();i++){a[i+1]=min(a[i]+diff[i],maxVal[i+1]);}for(inti=n-2;i>0;i--){a[i]=min(a[i],a[i+1]+diff[i]);}return*max_element(a.begin(),a.end());}intmain(){intn=10;vector<vector<int>>restrictions={{3,1},{8,1}};vector<int>diff={2,2,3,1,4,5,1,1,2};intresult=findMaxVal(n,restrictions,diff);cout<<result<<endl;return0;}