第 173 场双周赛Q3——3796. 找到带限制序列的最大值

题目链接：3796. 找到带限制序列的最大值（中等）

算法原理：

解法：双向约束传递

10ms击败54.10%

时间复杂度O(N)

①初始化约束数组：创建数组maxA记录每个位置的最大可行值，初始设为极大值（表示无约束），并固定a[0]=0
②应用硬限制：将restrictions中指定位置idx的最大允许值直接赋值给maxA[idx]，优先满足显式位置限制
③左到右约束传递：遍历序列（从 1 到 n-1），确保每个位置i满足 a[i] ≤ a[i-1] + diff[i-1]，取maxA[i]与该约束值的较小值更新maxA[i]（保证不违反左到右的差值约束）
④右到左约束传递：反向遍历序列（从 n-2 到 0），确保每个位置i满足 a[i] ≤ a[i+1] + diff[i]，同样取较小值更新maxA[i]（保证不违反右到左的差值约束）
⑤计算最终结果：遍历maxA数组，取所有值中的最大值（且保证非负），转为 int 返回

Java代码：

class Solution { public int findMaxVal(int n, int[][] restrictions, int[] diff) { //初始化每个位置的最大可能值为极大值 long[] maxA=new long[n]; Arrays.fill(maxA,Long.MAX_VALUE); //初始条件：a[0]=0; maxA[0]=0; //应用限制条件:restrictions中的位置idx不能超过maxVal for(int[] r:restrictions){ int idx=r[0]; int maxVal=r[1]; maxA[idx]=maxVal; } //从左到右遍历：约束a[i]<=a[i-1]+diff[i-1] for(int i=1;i<n;i++) if(maxA[i-1]!=Long.MAX_VALUE) maxA[i]=Math.min(maxA[i],maxA[i-1]+diff[i-1]); //从右到左遍历：约束a[i]<=a[i+1]+diff[i] for(int i=n-2;i>=0;i--) if(maxA[i]!=Long.MAX_VALUE) maxA[i]=Math.min(maxA[i],maxA[i+1]+diff[i]); //计算序列中的最大值（保证非负） long maxVal=0; for(long val:maxA) maxVal=Math.max(maxVal,Math.max(val,0)); return (int)maxVal; } }