Medium

题目描述

给你一个整数 n，表示一个长度为 n 的数组 colors，其中所有元素都被设置为 0，表示未着色。同时给你一个二维整数数组 queries，其中 queries[i] = [indexi, colori]。

对于第 i 个查询：

  • 将 colors[indexi] 设置为 colori
  • 统计 colors 中颜色相同的相邻对的数量（无论 colori 的值如何）

返回一个与 queries 长度相同的数组 answer，其中 answer[i] 是第 i 个查询的答案。

示例 1：

输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
输出：[0,1,1,0,2]

解释：
- 初始时 colors = [0,0,0,0]，其中 0 表示数组中未着色的元素
- 第 1 次查询后 colors = [2,0,0,0]。颜色相同的相邻对数量为 0
- 第 2 次查询后 colors = [2,2,0,0]。颜色相同的相邻对数量为 1
- 第 3 次查询后 colors = [2,2,0,1]。颜色相同的相邻对数量为 1
- 第 4 次查询后 colors = [2,1,0,1]。颜色相同的相邻对数量为 0
- 第 5 次查询后 colors = [2,1,1,1]。颜色相同的相邻对数量为 2

示例 2：

输入：n = 1, queries = [[0,100000]]
输出：[0]

解释：
第 1 次查询后 colors = [100000]。颜色相同的相邻对数量为 0。

约束条件：

  • 1 <= n <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= indexi <= n - 1
  • 1 <= colori <= 10^5

解题思路

解题思路

这道题的关键在于理解每次修改颜色时，只会影响当前位置与其相邻位置的配对关系。我们不需要每次都重新计算整个数组的相邻相同对数量，而是可以通过增量更新来高效解决。

核心思路：

  1. 维护计数器：用一个变量 count 记录当前相邻相同对的总数量
  2. 局部影响分析：每次修改位置 i 的颜色时，只需要考虑位置 i 与其左邻居 i-1 和右邻居 i+1 的关系变化
  3. 增量更新：
    • 修改前：如果 colors[i] 与左邻居或右邻居颜色相同且都不为0，则 count--
    • 修改后：如果新的 colors[i] 与左邻居或右邻居颜色相同，则 count++

实现要点：

  • 初始化数组全为0（未着色状态）
  • 对于每个查询，先减去原有的相邻相同对，然后更新颜色，最后加上新产生的相邻相同对
  • 边界处理：注意数组边界，避免越界访问
  • 0值处理：未着色的0不参与相邻相同对的计算

时间复杂度为 O(q)，其中 q 是查询次数，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
        vector<int> colors(n, 0);
        vector<int> result;
        int count = 0;
        
        for (auto& query : queries) {
            int index = query[0];
            int newColor = query[1];
            
            // 减去修改前的相邻相同对
            if (index > 0 && colors[index] != 0 && colors[index] == colors[index-1]) {
                count--;
            }
            if (index < n-1 && colors[index] != 0 && colors[index] == colors[index+1]) {
                count--;
            }
            
            // 更新颜色
            colors[index] = newColor;
            
            // 加上修改后的相邻相同对
            if (index > 0 && colors[index-1] != 0 && colors[index] == colors[index-1]) {
                count++;
            }
            if (index < n-1 && colors[index+1] != 0 && colors[index] == colors[index+1]) {
                count++;
            }
            
            result.push_back(count);
        }
        
        return result;
    }
};

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        colors = [0] * n
        result = []
        count = 0
        
        for index, new_color in queries:
            # 减去修改前的相邻相同对
            if index > 0 and colors[index] != 0 and colors[index] == colors[index-1]:
                count -= 1
            if index < n-1 and colors[index] != 0 and colors[index] == colors[index+1]:
                count -= 1
            
            # 更新颜色
            colors[index] = new_color
            
            # 加上修改后的相邻相同对
            if index > 0 and colors[index-1] != 0 and colors[index] == colors[index-1]:
                count += 1
            if index < n-1 and colors[index+1] != 0 and colors[index] == colors[index+1]:
                count += 1
            
            result.append(count)
        
        return result

public class Solution {
    public int[] ColorTheArray(int n, int[][] queries) {
        int[] colors = new int[n];
        int[] result = new int[queries.Length];
        int count = 0;
        
        for (int i = 0; i < queries.Length; i++) {
            int index = queries[i][0];
            int newColor = queries[i][1];
            
            // 减去修改前的相邻相同对
            if (index > 0 && colors[index] != 0 && colors[index] == colors[index-1]) {
                count--;
            }
            if (index < n-1 && colors[index] != 0 && colors[index] == colors[index+1]) {
                count--;
            }
            
            // 更新颜色
            colors[index] = newColor;
            
            // 加上修改后的相邻相同对
            if (index > 0 && colors[index-1] != 0 && colors[index] == colors[index-1]) {
                count++;
            }
            if (index < n-1 && colors[index+1] != 0 && colors[index] == colors[index+1]) {
                count++;
            }
            
            result[i] = count;
        }
        
        return result;
    }
}

var colorTheArray = function(n, queries) {
    const colors = new Array(n).fill(0);
    const result = [];
    let count = 0;
    
    for (const [index, newColor] of queries) {
        // 减去修改前的相邻相同对
        if (index > 0 && colors[index] !== 0 && colors[index]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(q)其中 q 是查询次数，每次查询只需要常数时间处理
空间复杂度O(n)需要额外的数组存储颜色状态