2672-有相同颜色的相邻元素数目

给你一个下标从 0 开始、长度为 n 的数组 nums 。一开始，所有元素都是 未染色 （值为 0 ）的。

给你一个二维整数数组 queries ，其中 queries[i] = [indexi, colori] 。

对于每个操作，你需要将数组 nums 中下标为 indexi 的格子染色为 colori 。

请你返回一个长度与 queries 相等的数组 _ _answer _ _ ，其中 _ _answer[i]是前 i 个操作 之后
，相邻元素颜色相同的数目。

更正式的，answer[i] 是执行完前 i 个操作后，0 <= j < n - 1 的下标 j 中，满足 nums[j] == nums[j + 1] 且 nums[j] != 0 的数目。

示例 1：

**输入：** n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
**输出：** [0,1,1,0,2]
**解释：** 一开始数组 nums = [0,0,0,0] ，0 表示数组中还没染色的元素。
- 第 1 个操作后，nums = [2,0,0,0] 。相邻元素颜色相同的数目为 0 。
- 第 2 个操作后，nums = [2,2,0,0] 。相邻元素颜色相同的数目为 1 。
- 第 3 个操作后，nums = [2,2,0,1] 。相邻元素颜色相同的数目为 1 。
- 第 4 个操作后，nums = [2,1,0,1] 。相邻元素颜色相同的数目为 0 。
- 第 5 个操作后，nums = [2,1,1,1] 。相邻元素颜色相同的数目为 2 。

示例 2：

**输入：** n = 1, queries = [[0,100000]]
**输出：** [0]
**解释：** 一开始数组 nums = [0] ，0 表示数组中还没染色的元素。
- 第 1 个操作后，nums = [100000] 。相邻元素颜色相同的数目为 0 。

提示：

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

本题视频讲解

见【周赛 344】 第三题，欢迎点赞投币！

思路

由于每次修改只会影响当前元素与其左右元素的关系，所以模拟即可。

用 cnt 统计相邻相同的个数。

代码实现时，可以先去掉当前元素对 cnt 的影响，修改颜色后，再加上当前元素对 cnt 的影响。

[sol1-Python3]

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        ans = []
        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况
        for i, c in queries:
            i += 1  # 下标改成从 1 开始
            if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])
            a[i] = c
            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])
            ans.append(cnt)
        return ans

[sol1-Java]

class Solution {
    public int[] colorTheArray(int n, int[][] queries) {
        int q = queries.length, cnt = 0;
        int[] ans = new int[q], a = new int[n + 2]; // 避免讨论下标出界的情况
        for (int qi = 0; qi < q; qi++) {
            int i = queries[qi][0] + 1, c = queries[qi][1]; // 下标改成从 1 开始
            if (a[i] > 0)
                cnt -= (a[i] == a[i - 1] ? 1 : 0) + (a[i] == a[i + 1] ? 1 : 0);
            a[i] = c;
            cnt += (a[i] == a[i - 1] ? 1 : 0) + (a[i] == a[i + 1] ? 1 : 0);
            ans[qi] = cnt;
        }
        return ans;
    }
}

[sol1-C++]

class Solution {
public:
    vector<int> colorTheArray(int n, vector<vector<int>> &queries) {
        int q = queries.size(), cnt = 0;
        vector<int> ans(q), a(n + 2); // 避免讨论下标出界的情况
        for (int qi = 0; qi < q; qi++) {
            int i = queries[qi][0] + 1, c = queries[qi][1]; // 下标改成从 1 开始
            if (a[i]) cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1]);
            a[i] = c;
            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1]);
            ans[qi] = cnt;
        }
        return ans;
    }
};

[sol1-Go]

func colorTheArray(n int, queries [][]int) []int {
	ans := make([]int, len(queries))
	a := make([]int, n+2) // 避免讨论下标出界的情况
	cnt := 0
	for qi, q := range queries {
		i, c := q[0]+1, q[1] // 下标改成从 1 开始
		if a[i] > 0 {
			if a[i] == a[i-1] {
				cnt--
			}
			if a[i] == a[i+1] {
				cnt--
			}
		}
		a[i] = c
		if a[i] == a[i-1] {
			cnt++
		}
		if a[i] == a[i+1] {
			cnt++
		}
		ans[qi] = cnt
	}
	return ans
}

复杂度分析

• 时间复杂度：\mathcal{O}(n+q)，其中 q 为 queries 的长度。
• 空间复杂度：\mathcal{O}(n)。

思考题

如果求的是最长连续同色长度要怎么做？