Как решить MaxCounters - Совместимость с Golang

Question

Вам дан массив счетчиков N, начатый с нуля.

У вас есть список действий A, которые нужно выполнить с массивом N.

каждое действие - int x

ie A = [1,5,3]

для каждого k в A как x действий

• если x <= len (N), то увеличить N [i-1] на один </li>
• еще установить все N элементы с максимальным значением N

вы должны вернуть массив counters после последнего действия

Упражнение Link

Answer 1

Первое и более простое решение

• не пройдет 100% из-за сложности времени

• создать массив counters со всеми 0 по размеруlen(A)

• для каждого idx, action в A
• , если action <= <code>len(N)
  • counters[idx-1]++
• else
  • maxVal = max(counters)
  • теперь установите max maxVal для всех counters элементов

• возврат counters

• небольшое улучшение, сохраняйте переменную maxVal в верхней части и обновляйте ее при каждом увеличении счетчиков.Затем, когда вам нужно установить все элементы, вам не нужно находить max значение.

Лучшее решение

, которое проходит тесты 100%

Мы по-прежнему будем выполнять действия, и мы сохраняем максимальное значение и другую новую переменную forcedVal.мы не будем обновлять весь массив счетчиков каждый раз, когда нам нужно, а только обновим forcedVal с макс.Затем, когда нам понадобится ++ элемент, мы сначала проверим, меньше ли он, чем forcedVal, и если да, мы передадим ему значение forcedVal перед созданием ++.

• .counters массив со всеми 0 размером len(A)
• create max var с 0
• create forcedVal var с 0
• для каждого idx, action в A
• , если action <= <code>len(N)
  • cur = counters[idx-1]
  • if cur < forceVal ? cur = forceVal
  • cur ++
  • если cur> max
  • max = cur
  • счетчики [idx-1] = cur

• else

  • forcedVal = max

• здесь мы делаем один цикл для установки наших счетчиков

• для каждого центав счетчиках
  • , если cnt <принудительное вычисление?cnt = принудительное вычисление </li>
• return 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
}