leetcode1943_go_描述绘画结果

题目

给你一个细长的画，用数轴表示。这幅画由若干有重叠的线段表示，每个线段有独一无二的颜色。

给你二维整数数组 segments ，

其中 segments[i] = [starti, endi, colori] 表示线段为半开区间 [starti, endi) 且颜色为 colori 。

线段间重叠部分的颜色会被混合。如果有两种或者更多颜色混合时，它们会形成一种新的颜色，用一个集合表示这个混合颜色。

比方说，如果颜色 2 ，4 和 6 被混合，那么结果颜色为 {2,4,6} 。

为了简化题目，你不需要输出整个集合，只需要用集合中所有元素的和来表示颜色集合。

你想要用最少数目不重叠半开区间来表示这幅混合颜色的画。这些线段可以用二维数组 painting 表示，

其中 painting[j] = [leftj, rightj, mixj] 表示一个半开区间[leftj, rightj) 的颜色和为 mixj 。

比方说，这幅画由 segments = [[1,4,5],[1,7,7]] 组成，那么它可以表示为 painting = [[1,4,12],[4,7,7]] ，因为：

[1,4) 由颜色 {5,7} 组成（和为 12），分别来自第一个线段和第二个线段。

[4,7) 由颜色 {7} 组成，来自第二个线段。

请你返回二维数组 painting ，它表示最终绘画的结果（没有被涂色的部分不出现在结果中）。

你可以按任意顺序返回最终数组的结果。

半开区间 [a, b) 是数轴上点 a 和点 b 之间的部分，包含点 a 且不包含点 b 。

示例 1：输入：segments = [[1,4,5],[4,7,7],[1,7,9]] 输出：[[1,4,14],[4,7,16]]

解释：绘画借故偶可以表示为：

- [1,4) 颜色为 {5,9} （和为 14），分别来自第一和第二个线段。

- [4,7) 颜色为 {7,9} （和为 16），分别来自第二和第三个线段。

示例 2：输入：segments = [[1,7,9],[6,8,15],[8,10,7]] 输出：[[1,6,9],[6,7,24],[7,8,15],[8,10,7]]

解释：绘画结果可以以表示为：

- [1,6) 颜色为 9 ，来自第一个线段。

- [6,7) 颜色为 {9,15} （和为 24），来自第一和第二个线段。

- [7,8) 颜色为 15 ，来自第二个线段。

- [8,10) 颜色为 7 ，来自第三个线段。

示例 3：输入：segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]] 输出：[[1,4,12],[4,7,12]]

解释：绘画结果可以表示为：

- [1,4) 颜色为 {5,7} （和为 12），分别来自第一和第二个线段。

- [4,7) 颜色为 {1,11} （和为 12），分别来自第三和第四个线段。

注意，只返回一个单独的线段 [1,7) 是不正确的，因为混合颜色的集合不相同。

提示：1 <= segments.length <= 2 * 104

segments[i].length == 3

1 <= starti < endi <= 105

1 <= colori <= 109

每种颜色 colori 互不相同。

解题思路分析

1、双差分数组；时间复杂度O(n)，空间复杂度O(n)

func splitPainting(segments [][]int) [][]int64 {
   res := make([][]int64, 0)
   arr1 := make([]int64, 100005) // 和
   arr2 := make([]int64, 100005) // 次数
   n := len(segments)
   for i := 0; i < n; i++ {
      start := segments[i][0]
      end := segments[i][1]
      count := segments[i][2]
      arr1[start], arr2[start] = arr1[start]+int64(count), arr1[start]+1
      arr1[end], arr2[end] = arr1[end]-int64(count), arr1[end]-1
   }
   prevIndex := -1
   var prev1, prev2 int64
   var sum1, sum2 int64
   for i := 1; i < 100005; i++ {
      sum1 = sum1 + arr1[i]
      sum2 = sum2 + arr2[i]
      if sum1 > 0 {
         if prevIndex == -1 { // 之前不为-1，开头
            prevIndex = i
            prev1, prev2 = sum1, sum2
         } else if prev1 != sum1 { // 和不同，加入区间
            res = append(res, []int64{int64(prevIndex), int64(i), prev1})
            prevIndex = i
            prev1, prev2 = sum1, sum2
         } else {
            if prev2 != sum2 { // 次数不同。加入区间
               res = append(res, []int64{int64(prevIndex), int64(i), prev1})
               prevIndex = i
               prev1, prev2 = sum1, sum2
            }
         }
      } else if sum1 == 0 {
         if prevIndex > 0 { // 和为0，之前不为0，加入区间
            res = append(res, []int64{int64(prevIndex), int64(i), prev1})
            prevIndex = -1
            prev1, prev2 = sum1, sum2
         }
      }
   }
   return res
}

2、差分数组+前缀和；时间复杂度O(nlog(n))，空间复杂度O(n)

func splitPainting(segments [][]int) [][]int64 {
   res := make([][]int64, 0)
   m := make(map[int]int)
   for i := 0; i < len(segments); i++ {
      start := segments[i][0]
      end := segments[i][1]
      count := segments[i][2]
      m[start] = m[start] + count
      m[end] = m[end] - count
   }
   arr := make([][2]int, 0)
   for k, v := range m {
      arr = append(arr, [2]int{k, v})
   }
   sort.Slice(arr, func(i, j int) bool {
      return arr[i][0] < arr[j][0]
   })
   n := len(arr)
   for i := 1; i < n; i++ { // 前缀和
      arr[i][1] = arr[i][1] + arr[i-1][1]
   }
   for i := 0; i < n-1; i++ {
      if arr[i][1] > 0 { // 和大于0
         res = append(res, []int64{
            int64(arr[i][0]),
            int64(arr[i+1][0]),
            int64(arr[i][1]),
         })
      }
   }
   return res
}

3、差分数组+哈希；时间复杂度O(n)，空间复杂度O(n)

func splitPainting(segments [][]int) [][]int64 {
   res := make([][]int64, 0)
   arr := make([]int64, 100005) // 和
   m := make([]bool, 100005)
   n := len(segments)
   for i := 0; i < n; i++ {
      start := segments[i][0]
      end := segments[i][1]
      count := segments[i][2]
      arr[start] = arr[start] + int64(count)
      arr[end] = arr[end] - int64(count)
      m[start] = true
      m[end] = true
   }
   var sum int64
   var prev int64
   for i := 1; i < 100005; i++ {
      if m[i] == true {
         if sum > 0 {
            res = append(res, []int64{prev, int64(i), sum})
         }
         sum = sum + arr[i]
         prev = int64(i)
      }
   }
   return res
}