[解題]HackerRank-Algorithmic Crush(Hard)

題目敘述：

Devendra在9号云上看到了他的教练朝他微笑。 每次教授选出Devendra单独问他一个问题，Devendra朦胧的头脑里全是他的教练和她的微笑，以至于他无法专注于其他事情。帮助他解决这个问题：

给你一个长度为N的列表，列表的初始值全是0。对此列表，你要进行M次查询，输出列表种最终N个值的最大值。对每次查询，给你的是3个整数 — — a,b和k，你要对列表中从位置a到位置b范围内的（包含a和b)的全部元素加上k。

输入格式

第一行包含两个整数 N和 M。
接下来 M行，每行包含3个整数 a, b 和 k。
列表中的数位置编号为从1到 N。

输出格式

单独的一行包含 最终列表里的最大值

其中輸入限制為：

3 <= N <= 10⁷
1 <= M <= 2*10⁵
1 <= a <= b <= N
0 <= k <= 10⁹

看完題目就可以開始想解法囉，以下會提供兩種思路，一種是很直覺的暴力解(但是會TLE)，另一種則是在Discussion裡看到的大神解答。

1. 暴力解

第一種很簡單的做法就是給妳幾個query，把每個query給的區間每格都填值上去：

long arrayManipulation(int n, vector<vector<int>> queries) {
    vector<long>arr(n,0);
    long ans = 0;
    int len = queries.size();
    for(int i = 0;i<len;i++)
    {
        for(int j=queries[i][0]-1;j<queries[i][1];j++)
        {
            arr[j]+=queries[i][2];
            ans = max(arr[j], ans);
        }
    }
    return ans;
}

如果有特別注意輸入限制的話，使用暴力解的最差情況的複雜度會來到O(10⁷ * 2*10⁵)，一定會TLE的，因此此方法雖然可以找出解答，但時間上是會被打槍的。

2. 區間解

此方法為Discussion裡面的大神解，我個人認為此思路跟two pointers有點類似，作法則是把每個query的區間起始位置加上k，表示此區間的值都等同於起始區間，區間結束後填上一個負k，表示此區間的結束。

其實還蠻難解釋的，看下例後就會對此方法更了解了

ex: query = [ [1, 9, 100] , [2, 5, 100] ]

arr[10]: 為長度10的陣列，初始值皆為零(index從1開始，舉例用)

當處理query 1後，arr = [100, 0, 0, 0, 0, 0, 0, 0, 0, -100]

處理query 2後，arr = [100, 100, 0, 0, 0, -100, 0, 0, 0, -100]

要怎麼找出最此陣列裡面的最大值呢，很簡單，從頭開始往後加，加到0代表在同區間裡面，加到正整數就是進入新區間，加到負整數就是離開一個區間

而我們只要處理完所有的query之後，再用O(N)的時間去找出最大值就好了，最差的情況則是O(2*N) = O(N)，比上面的暴力解快了一個量級。

說了這麼多，還是看code最好了解了：

long arrayManipulation(int n, vector<vector<int>> queries) {
    vector<long>arr(n+1,0);
    long ans = 0;
    int len = queries.size();
    for(int i = 0;i<len;i++)
    {
        arr[queries[i][0]] += queries[i][2]; // 區間頭
        if(queries[i][1]+1 <= n)arr[queries[i][1]+1] -= queries[i][2];// 判斷區間尾
    }
    for(int i=1;i<arr.size();i++)
    {
        arr[i]+= arr[i-1];
        ans = max(ans,arr[i]);
    }
    return ans;
}

後記

多寫之後真的會碰到很多自己想不出來的題目，其實不太需要難過，也不要耗太久時間在想，我覺得最多想15分鐘，之後可以去Discussion看其他人的解法。當然不是要你背code，是要你了解其他人的思考邏輯，所以有step by step講解的留言是最好的，有時候看到妖魔鬼怪的解法，但根本看不懂為什麼這樣寫的情況也是不少的。

寫完這題後覺得值得紀念，就回來打一篇文章，紀錄一下自己的收穫。