MaxCounters

發表於 | 分類於 ，

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(int N, vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)

    int counter = 0, before = 0, n = A.size();
    vector<int> ret(N,0);
    for(int a:A){
        if(a!=N+1){
            // 延遲assign max counter
            if(before!=0 && ret[a-1]!=before) ret[a-1] = max(before, ret[a-1]);
            ret[a-1]++;
            // update max counter
            counter = max(counter, ret[a-1]);
        }
        else{
            before = counter;
        }
        // for(int a:ret) cout<<a<<" ";
        // cout<<endl;
    }
    // for(int a:ret) cout<<a<<" ";
    for(int &a:ret){
        a = max(a, before);
    }
    return ret;
}

analysis

  • time complexity O(n+m), m is the number of array A
  • space complexity O(1)