leetcode 798. Smallest Rotation with Highest Score

Given an array A, we may rotate it by a non-negative integer K so that the array becomes A[K], A[K+1], A{K+2], ... A[A.length - 1], A[0], A[1], ..., A[K-1].  Afterward, any entries that are less than or equal to their index are worth 1 point. 

For example, if we have [2, 4, 1, 3, 0], and we rotate by K = 2, it becomes [1, 3, 0, 2, 4].  This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point].

Over all possible rotations, return the rotation index K that corresponds to the highest score we could receive.  If there are multiple answers, return the smallest such index K.

Example 1:
Input: [2, 3, 1, 4, 0]
Output: 3
Explanation:  
Scores for each K are listed below: 
K = 0,  A = [2,3,1,4,0],    score 2
K = 1,  A = [3,1,4,0,2],    score 3
K = 2,  A = [1,4,0,2,3],    score 3
K = 3,  A = [4,0,2,3,1],    score 4
K = 4,  A = [0,2,3,1,4],    score 3

So we should choose K = 3, which has the highest score.

Example 2:
Input: [1, 3, 0, 2, 4]
Output: 0
Explanation:  A will always have 3 points no matter how it shifts.
So we will choose the smallest K, which is 0.

Note:

• A will have length at most 20000.
• A[i] will be in the range [0, A.length].

解题思路：

当i>=k时， A[i] <= i - k ; =>  0 <= k <= min(i , i - A[i]) 因为A[i] >= 0 , 所以 0 <= k <= i - A[i] ;

当i < k 时 ， A[i] <= i + n - k ; => i + 1 <= k <= i + n - A[i]

当i - A[i] >= 0 ， k的得分区间为 [0 , i - A[i] ] 和 [i + 1 , n - 1 ] ;

当 i - A[i] < 0 ， k的得分区间为 [i + 1 , i + n - A[i] ] ；

我一开始将区间内的k都加1 ， 然后找score中的最大值对应的k值，时间复杂度近乎O(logN^2)

class Solution {
public:
    int bestRotation(vector<int>& A) 
    {
        int n = A.size() ;
        vector<int> score(n , 0) ;
        int mxs = -1 , mxk ;
        vector<int> inter(4 , 0) ;
        
        for(int i = 0 ; i < n ; ++i)
        {

            inter[1] = min(i , i - A[i]) ;
            inter[2] = i + 1;
            inter[3] = i + n - A[i] ;
            change(inter , score) ;
        }
        
        for(int i = 0 ; i < n ; ++i)
        {
            if(score[i] > mxs) 
            {
                mxs = score[i] ;
                mxk = i ;
            }
        }
        
        return mxk ;
    }
    
    void change(vector<int>& inter , vector<int> &s)
    {
        for(int i = 0 ; i < inter.size() ; i += 2)
        {
            int left = inter[i] , right = inter[i + 1] ;

            while(left < s.size() && left <= right)
            {
                s[left++]++;
            }
        }
    }
};

然后就超时了。。。

然后我发现了一种方法巨好用！不用将区间中值都加1， 只用score[left]++ , score[right + 1]--，然后计算score数组中k的前缀和就可以了！

时间复杂度只有O(N) ；

class Solution {
public:
    int bestRotation(vector<int>& A) 
    {
        int n = A.size() , mxs = -1 , mxk = -1 , prevsum = 0 ;
        vector<int> score(n + 1 , 0) ;
        
        for(int i = 0 ; i < n ; ++i)
        {
            if(A[i] >= n) continue ;
            if(i >= A[i])
            {
                score[0]++ ;
                score[i - A[i] + 1]--;
                score[i + 1]++ ;
                
            }
            else
            {
                score[i + 1]++;
                score[i + n - A[i] + 1]-- ;
            }
        }
        
        for(int i = 0 ; i < n ; ++i)
        {
            prevsum += score[i] ;
            if(prevsum > mxs)
            {
                mxs = prevsum ;
                mxk = i ;
            }
        }
        
        return mxk ;
    }
};