2026-05-10：找到帶限制序列的最大值。用go語言，給定一個整數(shù) n、一個二維整數(shù)數(shù)組 restrictions、以及一個長度為 n-1 的數(shù)組 diff。你需要生成一個長度為 n 的非負整數(shù)序列 a[0…n-1]，使得：

• ? a[0] 固定為 0。

• ? 對于每個 i（0 ≤ i ≤ n-2），相鄰項差的絕對值不超過給定限制：|a[i] - a[i+1]| ≤ diff[i]。

• ? 對于 restrictions 中的每一項 [idx, maxVal]，都要保證對應(yīng)位置滿足：a[idx] ≤ maxVal。

在所有滿足上述條件的序列中，你的目標是讓序列里的“最大元素值”盡可能大。最終輸出這個最大元素值的最優(yōu)結(jié)果。

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。

詳細步驟

我會完全脫離代碼，用純文字、分步驟把整個解題過程講清楚，同時最后給出時間和空間復(fù)雜度。

一、先明確題目核心規(guī)則

我們要構(gòu)造一個長度為n的序列a，滿足：

1. 1. 起點固定：a[0] = 0

2. 2. 相鄰約束：|a[i] - a[i+1]| ≤ diff[i]（相鄰兩個數(shù)的差值絕對值不能超過對應(yīng)diff值）

3. 3. 點位約束：指定下標idx的值必須 ≤ 給定的maxVal

4. 4. 目標：在所有合法序列中，讓整個序列的最大值盡可能大，求這個最大可能值

整個算法的核心邏輯是：
先從左到右推導(dǎo)出每個位置能達到的理論最大值，再從右到左修正所有違反相鄰約束和點位約束的值，最終得到合法的最優(yōu)序列，再取最大值。

下面是分步驟詳細過程：

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

1. 1. 給序列的每一個位置0~n-1都設(shè)置一個初始最大允許值，默認是無窮大（表示暫時沒有限制）。

2. 2. 遍歷所有的restrictions點位約束：

• ? 把對應(yīng)下標的硬上限直接修改為題目給定的maxVal。

• ? 比如約束[3,1]，就把位置3的硬上限設(shè)為1；[8,1]就把位置8的硬上限設(shè)為1。

• ? 其他沒有約束的位置，上限保持無窮大。

這一步的作用：先把所有固定的點位限制記下來，后續(xù)推導(dǎo)不能超過這些值。

步驟2：從左到右遍歷，計算「左向最大可能值」

從起點a[0]=0開始，向右依次計算每個位置能達到的最大理論值：

1. 1. 起點固定：a[0] = 0

2. 2. 對于第i+1個位置：

• ? 它的理論最大值= 左邊位置i的值 + 相鄰允許的最大增量diff[i]

• ? 同時不能超過該位置的硬上限（步驟1設(shè)置的值）

• ? 最終取兩者中的較小值作為當(dāng)前位置的左向最大值

這一步的邏輯：只能向右走，每次最多加diff[i]，同時不能碰點位限制。
這一步結(jié)束后，得到的序列滿足：

• ? 從左到右的相鄰約束

• ? 所有點位硬上限約束

• ? 但不滿足從右到左的相鄰約束（右邊的值可能太大，導(dǎo)致和左邊的差值超標）

從最后一個位置開始，向左依次修正每個位置的值，讓序列同時滿足左右雙向的相鄰約束：

1. 1. 從倒數(shù)第二個位置開始，向左遍歷到第1個位置

2. 2. 對于當(dāng)前位置i：

• ? 它的最大合法值= 右邊位置i+1的值 + 相鄰允許的最大增量diff[i]

• ? 同時不能超過步驟2算出的左向最大值

• ? 最終取兩者中的較小值作為當(dāng)前位置的最終值

這一步的作用：修正左到右推導(dǎo)時，右側(cè)值過大導(dǎo)致的左側(cè)不合法問題，讓整個序列同時滿足：

• ? 起點固定

• ? 所有相鄰雙向約束

• ? 所有點位約束

• ? 且序列中的每個值都是當(dāng)前約束下能取到的最大值（保證整體最大值最優(yōu)）

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

三、用題目示例驗證過程（直觀理解）

輸入：

• ?n=10，序列長度10

• ? 約束：[3,1]、[8,1]

• ?diff = [2,2,3,1,4,5,1,1,2]

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

步驟2：左→右推導(dǎo)（取最大理論值）

• ? 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

左→右結(jié)果：[0,2,4,1,2,6,11,12,1,3]
（這個序列不合法：比如12和1的差值遠超diff限制）

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

從右往左依次修正，讓相鄰差值合規(guī)：
最終得到合法最優(yōu)序列：[0,2,4,1,2,6,2,1,1,3]
（和題目解釋的序列完全一致）

步驟4：取最大值

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

四、時間復(fù)雜度 & 額外空間復(fù)雜度 1. 總時間復(fù)雜度

整個過程只涉及三次線性遍歷：

1. 1. 初始化上限數(shù)組：O(n)

2. 2. 左→右遍歷：O(n)

3. 3. 右→左遍歷：O(n)

4. 4. 求序列最大值：O(n)

所有操作都是和序列長度n成正比的線性操作，沒有嵌套循環(huán)。
?總時間復(fù)雜度：O(n)

2. 總額外空間復(fù)雜度

我們額外開辟了兩個數(shù)組：

1. 1. 存儲每個位置硬上限的數(shù)組：長度n

2. 2. 存儲最終序列的數(shù)組：長度n

其他變量都是常數(shù)級空間，不隨n變化。
?總額外空間復(fù)雜度：O(n)

總結(jié)

1. 1. 解題分四步：初始化點位上限 → 左向右推最大理論值 → 右向左修正合規(guī)值 → 取序列最大值；

2. 2. 核心是通過兩次遍歷同時滿足所有約束，并讓序列最大值最優(yōu)；

3. 3. 時間復(fù)雜度：O(n)（線性效率，適合n≤10萬的大數(shù)據(jù)量）；

4. 4. 額外空間復(fù)雜度：O(n)（用兩個長度為n的輔助數(shù)組完成計算）。

package main

 import (
    "fmt"
    "math"
    "slices"
)

 func findMaxVal(n int, restrictions [][]int, diff []int)int {
    maxVal := make([]int, n)
    for i := range maxVal {
        maxVal[i] = math.MaxInt
    }
    for _, r := range restrictions {
        maxVal[r[0]] = r[1]
    }

     a := make([]int, n)
    for i, d := range diff {
        a[i+1] = min(a[i]+d, maxVal[i+1])
    }
    for i := n - 2; i > 0; i-- {
        a[i] = min(a[i], a[i+1]+diff[i])
    }
    return slices.Max(a)
}

 func main() {
    n := 10
    restrictions := [][]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-*-

 import math

 def find_max_val(n, restrictions, diff):
    max_val = [math.inf] * n
    for r in restrictions:
        max_val[r[0]] = r[1]

     a = [0] * n
    for i, d in enumerate(diff):
        a[i + 1] = min(a[i] + d, max_val[i + 1])
    for i in range(n - 2, 0, -1):
        a[i] = min(a[i], a[i + 1] + diff[i])
    return max(a)

 if __name__ == "__main__":
    n = 10
    restrictions = [[3, 1], [8, 1]]
    diff = [2, 2, 3, 1, 4, 5, 1, 1, 2]
    result = find_max_val(n, restrictions, diff)
    print(result)

C++完整代碼如下：

  

  

   


 using namespace std;

 int findMaxVal(int n, 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 
  ( 
 int 
  i =  
 0 
 ; i < diff.size(); i++) { 
 
 
         a[i +  
 1 
 ] = min(a[i] + diff[i], maxVal[i +  
 1 
 ]); 
 
 
     } 
 
 
 
 
      
 for 
  ( 
 int 
  i = n -  
 2 
 ; i >  
 0 
 ; i--) { 
 
 
         a[i] = min(a[i], a[i +  
 1 
 ] + diff[i]); 
 
 
     } 
 
 
 
 
      
 return 
  *max_element(a.begin(), a.end()); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  n =  
 10 
 ; 
 
 
     vector 
 
 int 
 >> restrictions = {{ 
 3 
 ,  
 1 
 }, { 
 8 
 ,  
 1 
 }}; 
 
 
     vector< 
 int 
 > diff = { 
 2 
 ,  
 2 
 ,  
 3 
 ,  
 1 
 ,  
 4 
 ,  
 5 
 ,  
 1 
 ,  
 1 
 ,  
 2 
 }; 
 
 
      
 int 
  result = findMaxVal(n, restrictions, diff); 
 
 
     cout << result << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 

我們相信人工智能為普通人提供了一種“增強工具”，并致力于分享全方位的AI知識。在這里，您可以找到最新的AI科普文章、工具評測、提升效率的秘籍以及行業(yè)洞察。 歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。