Question

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

English Version

题目描述

给你一个下标从 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

解法

方法一

class Solution:
  def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
    nums = [0] * n
    ans = [0] * len(queries)
    x = 0
    for k, (i, c) in enumerate(queries):
      if i > 0 and nums[i] and nums[i - 1] == nums[i]:
        x -= 1
      if i < n - 1 and nums[i] and nums[i + 1] == nums[i]:
        x -= 1
      if i > 0 and nums[i - 1] == c:
        x += 1
      if i < n - 1 and nums[i + 1] == c:
        x += 1
      ans[k] = x
      nums[i] = c
    return ans

class Solution {
  public int[] colorTheArray(int n, int[][] queries) {
    int m = queries.length;
    int[] nums = new int[n];
    int[] ans = new int[m];
    for (int k = 0, x = 0; k < m; ++k) {
      int i = queries[k][0], c = queries[k][1];
      if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
        --x;
      }
      if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
        --x;
      }
      if (i > 0 && nums[i - 1] == c) {
        ++x;
      }
      if (i < n - 1 && nums[i + 1] == c) {
        ++x;
      }
      ans[k] = x;
      nums[i] = c;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
    vector<int> nums(n);
    vector<int> ans;
    int x = 0;
    for (auto& q : queries) {
      int i = q[0], c = q[1];
      if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
        --x;
      }
      if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
        --x;
      }
      if (i > 0 && nums[i - 1] == c) {
        ++x;
      }
      if (i < n - 1 && nums[i + 1] == c) {
        ++x;
      }
      ans.push_back(x);
      nums[i] = c;
    }
    return ans;
  }
};

func colorTheArray(n int, queries [][]int) (ans []int) {
  nums := make([]int, n)
  x := 0
  for _, q := range queries {
    i, c := q[0], q[1]
    if i > 0 && nums[i] > 0 && nums[i-1] == nums[i] {
      x--
    }
    if i < n-1 && nums[i] > 0 && nums[i+1] == nums[i] {
      x--
    }
    if i > 0 && nums[i-1] == c {
      x++
    }
    if i < n-1 && nums[i+1] == c {
      x++
    }
    ans = append(ans, x)
    nums[i] = c
  }
  return
}

function colorTheArray(n: number, queries: number[][]): number[] {
  const nums: number[] = new Array(n).fill(0);
  const ans: number[] = [];
  let x = 0;
  for (const [i, c] of queries) {
    if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
      --x;
    }
    if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
      --x;
    }
    if (i > 0 && nums[i - 1] == c) {
      ++x;
    }
    if (i < n - 1 && nums[i + 1] == c) {
      ++x;
    }
    ans.push(x);
    nums[i] = c;
  }
  return ans;
}