如何解决MaxCounters-Golang的Coditility

You are given an array of counters N initiated with zero.

You have a list of actions A to perform on N array.

each action is an int x

ie A = [1,5,3]

for each k in A as x actions

• if x <= len(N) then increase N[i-1] by one
• else set all N items with max of max value of N

you should return the counters array after the last action

Exercise Link

The first and simpler solution

• wont pass 100% because of time complexity

• create counters array with all 0 in size of len(A)

• for each idx,action in A
• if action <= len(N)
  • counters[idx-1]++
• else
  • maxVal = max(counters)
  • now set max maxVal to all counters items

• return counters

• small improvement, store maxVal variable in the top and update it with each increase of the counter items. Then when you need to set all items, you dont need to find max value.

Better solution

that passes the tests 100%

We will still go through actions, and we store the max value and another new variable forcedVal. we will not update the whole counters array each time we need but only update the forcedVal with the max. Then when ever we need to ++ an item we will first check if it is smaller then forcedVal and if so we will give it forcedVal value before the ++.

• create counters array with all 0 in size of len(A)
• create max var with 0
• create forcedVal var with 0
• for each idx,action in A
• if action <= len(N)
  • cur = counters[idx-1]
  • if cur < forceVal ? cur = forceVal
  • cur++
  • if cur > max
  • max = cur
  • counters[idx-1] = cur

• else

  • forcedVal = max

• here we do a single loop to set our counters

• for each cnt in counters
  • if cnt < forcedVal ? cnt = forcedVal
• return counters

this is how it will look with this example

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         |

as you can see above after all we have left with:

3, 0, 1, 4, 0

we will our final cleanup loop to set all items to at least the value of forcedVal and we get

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
}