algorithm - 如何解决 MaxCounters - Coditility with Golang

Question

你得到一个计数器数组N，从零开始。

您有一个要在 N 数组上执行的操作列表 A。

每个 Action 都是一个 int x

即 A = [1,5,3]

对于 A 中的每个 k 作为 x 操作

• 如果 x <= len(N) 则将 N[i-1] 加一
• 否则设置所有 N 项的最大值为 N

你应该在最后一个 Action 之后返回计数器数组

Exercise Link

Answer 1

第一个更简单的解决方案

• 由于时间复杂度不会 100% 通过

• 创建 counters大小为 len(A) 的全为 0 的数组

• 每个idx , action在A
• 如果action <= len(N)
  • counters[idx-1]++
• 其他
  • maxVal = max(counters)
  • 现在将 max maxVal 设置为所有 counters项目

• 返回 counters

• 小改进，商店 maxVal顶部的变量并随着计数器项目的每次增加而更新它。然后当你需要设置所有项目时，你不需要找到max值(value)。

更好的解决方案

100% 通过测试

我们仍将执行操作，并存储最大值和另一个新变量 forcedVal .我们不会在每次需要时更新整个计数器数组，而只会更新 forcedVal。与最大。然后什么时候我们需要++我们将首先检查一个项目是否小于 forcedVal如果是这样，我们会给它forcedVal ++ 之前的值.

• 创建counters大小为 len(A) 的全为 0 的数组
• 创建max可变为 0
• 创建forcedVal可变为 0
• 每个idx , action在A
• 如果action <= len(N)
  • cur = counters[idx-1]
  • if cur < forceVal ? cur = forceVal
  • cur++
  • 如果电流 > 最大值
  • 最大=电流
  • 计数器[idx-1] = cur

• 其他

  • forcedVal = max

• 这里我们做一个循环来设置我们的计数器

• 对于计数器中的每个 cnt
  • 如果 cnt < forcedVal ? cnt = 强制值
• 返回counters

这是这个例子的样子

Solution(5, [3, 4, 4, 6, 1, 4, 4])

| c[0] | c[1] | c[2] | c[3] | c[4] | action | max | forcedVal |
|------|------|------|------|------|--------|-----|-----------|
| 0    | 0    | 0    | 0    | 0    | null   | 0   | 0         |
| 0    | 0    | 1    | 0    | 0    | 3      | 1   | 0         |
| 0    | 0    | 1    | 1    | 0    | 4      | 1   | 0         |
| 0    | 0    | 1    | 2    | 0    | 4      | 2   | 0         |
| 0    | 0    | 1    | 2    | 0    | 6      | 2   | 2         |
| 3    | 0    | 1    | 2    | 0    | 1      | 3   | 2         |
| 3    | 0    | 1    | 3    | 0    | 4      | 3   | 2         |
| 3    | 0    | 1    | 4    | 0    | 4      | 4   | 2         |

正如你在上面看到的那样，我们已经离开了:

3, 0, 1, 4, 0

我们将在最后的清理循环中将所有项目设置为至少 forcedVal 的值我们得到

3, 2, 2, 4, 2

func Solution(N int, A []int) []int {
    counters := make([]int, N)
    var max int
    var forcedVal int

    for _, v := range A {
        if v > N {
            forcedVal = max
        } else {
            cur := counters[v-1]
            if cur < forcedVal {
                cur = forcedVal
            }
            cur++
            if cur > max {
                max = cur
            }
            counters[v-1] = cur
        }
    }
    for i := range counters {
        if counters[i] < forcedVal {
            counters[i] = forcedVal
        }
    }
    return counters
}