如何在给定约束条件下构造数组并确定其最大可能值？

问题要求 #

构造长度为N的数组，需满足以下全部约束：

• 首元素固定为0：arr[0] = 0
• 相邻元素差值绝对值≤1：|arr[i] - arr[i-1]| ≤ 1
• 给定M个(x, y)约束对，要求arr[x] ≤ y
• 数组所有元素均为非负整数（注：测试案例中存在0值，推测原描述的“正整数”为笔误）

目标是在满足约束的前提下，找到数组中的最大可能值。

测试案例 #

测试案例1 #

• N = 5，M = 4
• 约束对：(1, 0)、(2, 0)、(3, 0)、(4, 0)
• 可行数组：[0, 0, 0, 0, 0]
• 答案：0

测试案例2 #

• N = 5，M = 1
• 约束对：(3, 0)
• 可行数组：[0, 1, 1, 0, 1]
• 答案：1

测试案例3 #

• N = 10，M = 1
• 约束对：(3, 1)
• 可行数组：[0, 1, 2, 1, 2, 3, 4, 5, 6, 7]
• 答案：7

测试案例4 #

• N = 10，M = 2
• 约束对：(1,1)、(3,4)
• 可行数组：[0,1,2,3,4,5,6,7,8,9]
• 答案：9

解法思路 #

要确定每个位置的最大允许值，需综合左右相邻限制与给定约束，步骤如下：

1. 初始化约束数组：创建长度为N的数组max_val，初始值设为极大值（如1e9）。将max_val[0]设为0，对每个约束对(x,y)，更新max_val[x] = min(max_val[x], y)。

2. 左到右遍历更新：从索引1到N-1，每个位置的最大允许值不能超过前一位置的值加1，即max_val[i] = min(max_val[i], max_val[i-1] + 1)。

3. 右到左遍历更新：从索引N-2到0，每个位置的最大允许值不能超过后一位置的值加1，即max_val[i] = min(max_val[i], max_val[i+1] + 1)。

4. 计算最大值：最终max_val数组中的最大值即为所求的数组最大可能值。

未通过案例验证 #

针对你提到的案例：N=10，M=3，约束对(3,20)、(7,50)、(9,1)：

1. 初始化max_val数组：

   • max_val[0] = 0，max_val[3] =20，max_val[7]=50，max_val[9]=1，其余为极大值。

2. 左到右遍历后：

   • max_val[1]=1，max_val[2]=2，max_val[3]=min(20, 2+1)=3，max_val[4]=4，max_val[5]=5，max_val[6]=6，max_val[7]=min(50,6+1)=7，max_val[8]=8，max_val[9]=min(1,8+1)=1。

3. 右到左遍历后：

   • max_val[8] = min(8,1+1)=2，max_val[7]=min(7,2+1)=3，max_val[6]=min(6,3+1)=4，max_val[5]=min(5,4+1)=5，max_val[4]=min(4,5+1)=4，max_val[3]=min(3,4+1)=3，max_val[2]=min(2,3+1)=2，max_val[1]=min(1,2+1)=1，max_val[0]=0。

4. 最终max_val数组为：[0,1,2,3,4,5,4,3,2,1]，最大值为5，这是该案例的正确答案。

内容的提问来源于stack exchange，提问作者sarvesh kumar