Medium

题目描述

给定一个整数 n，一个二维整数数组 restrictions，以及一个长度为 n-1 的整数数组 diff。你需要构造一个长度为 n 的序列，记为 a[0], a[1], …, a[n-1]，使其满足以下条件：

  • a[0] 为 0
  • 序列中所有元素都非负
  • 对于每个索引 i (0 <= i <= n-2)，abs(a[i] - a[i+1]) <= diff[i]
  • 对于每个 restrictions[i] = [idx, maxVal]，位置 idx 处的值不得超过 maxVal（即 a[idx] <= maxVal）

你的目标是构造一个有效序列，在满足所有上述条件的同时，最大化序列中的最大值。

返回这样一个最优序列中存在的最大值。

示例 1：

输入：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。

示例 2：

输入：n = 8, restrictions = [[3,2]], diff = [3,5,2,4,2,3,1]
输出：12
解释：序列 a = [0, 3, 3, 2, 6, 8, 11, 12] 满足给定约束（a[3] <= 2）。
序列中的最大值是 12。

约束条件：

  • 2 <= n <= 10^5
  • 1 <= restrictions.length <= n - 1
  • restrictions[i].length == 2
  • restrictions[i] = [idx, maxVal]
  • 1 <= idx < n
  • 1 <= maxVal <= 10^6
  • diff.length == n - 1
  • 1 <= diff[i] <= 10
  • restrictions[i][0] 的值是唯一的

解题思路

这道题的核心思想是贪心算法。我们需要为每个位置确定一个上界，然后在这个上界内选择最大可能的值。

解题思路：

  1. 初始化上界数组：首先为每个位置设置一个足够大的上界（如 10^9），然后根据限制条件更新这些上界。

  2. 处理显式限制：对于每个 restrictions[i] = [idx, maxVal]，直接设置 upper[idx] = maxVal。

  3. 从左到右传播约束：由于相邻元素的差值有限制，我们从左到右遍历，确保 upper[i+1] <= upper[i] + diff[i]。这保证了从位置 i 能够到达位置 i+1 的最大值约束。

  4. 从右到左传播约束：同样地，我们从右到左遍历，确保 upper[i] <= upper[i+1] + diff[i]。这保证了从位置 i+1 能够到达位置 i 的最大值约束。

  5. 找最大值：经过双向传播后，upper 数组中的每个值都是该位置能够取到的最大值。我们返回其中的最大值即可。

这种方法的正确性在于：通过双向传播，我们确保了每个位置的上界既满足显式限制，也满足相邻位置的差值约束。最终的序列可以通过贪心地在每个位置选择不超过其上界的最大值来构造。

时间复杂度：O(n + m)，其中 m 是限制条件的数量 空间复杂度：O(n)

代码实现

class Solution {
public:
    int findMaxVal(int n, vector<vector<int>>& restrictions, vector<int>& diff) {
        vector<int> upper(n, 1000000);
        upper[0] = 0;
        
        for (auto& restriction : restrictions) {
            int idx = restriction[0];
            int maxVal = restriction[1];
            upper[idx] = maxVal;
        }
        
        for (int i = 0; i < n - 1; i++) {
            upper[i + 1] = min(upper[i + 1], upper[i] + diff[i]);
        }
        
        for (int i = n - 1; i > 0; i--) {
            upper[i - 1] = min(upper[i - 1], upper[i] + diff[i - 1]);
        }
        
        return *max_element(upper.begin(), upper.end());
    }
};

class Solution:
    def findMaxVal(self, n: int, restrictions: List[List[int]], diff: List[int]) -> int:
        upper = [1000000] * n
        upper[0] = 0
        
        for idx, maxVal in restrictions:
            upper[idx] = maxVal
        
        for i in range(n - 1):
            upper[i + 1] = min(upper[i + 1], upper[i] + diff[i])
        
        for i in range(n - 1, 0, -1):
            upper[i - 1] = min(upper[i - 1], upper[i] + diff[i - 1])
        
        return max(upper)

public class Solution {
    public int FindMaxVal(int n, int[][] restrictions, int[] diff) {
        int[] upper = new int[n];
        Array.Fill(upper, 1000000);
        upper[0] = 0;
        
        foreach (var restriction in restrictions) {
            int idx = restriction[0];
            int maxVal = restriction[1];
            upper[idx] = maxVal;
        }
        
        for (int i = 0; i < n - 1; i++) {
            upper[i + 1] = Math.Min(upper[i + 1], upper[i] + diff[i]);
        }
        
        for (int i = n - 1; i > 0; i--) {
            upper[i - 1] = Math.Min(upper[i - 1], upper[i] + diff[i - 1]);
        }
        
        return upper.Max();
    }
}

var findMaxVal = function(n, restrictions, diff) {
    let upper = new Array(n).fill(1000000);
    upper[0] = 0;
    
    for (let [idx, maxVal] of restrictions) {
        upper[idx] = maxVal;
    }
    
    for (let i = 0; i < n - 1; i++) {
        upper[i + 1] = Math.min(upper[i + 1], upper[i] + diff[i]);
    }
    
    for (let i = n - 1; i > 0; i--) {
        upper[i - 1] = Math.min(upper[i - 1], upper[i] + diff[i - 1]);
    }
    
    return Math.max(...upper);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + m)
空间复杂度O(n)

其中 n 是序列长度，m 是限制条件的数量。时间复杂度主要来自于两次遍历数组和处理限制条件，空间复杂度用于存储上界数组。

相关题目