https://leetcode.com/contest/weekly-contest-75/problems/smallest-rotation-with-highest-score/

1st version:

36 / 36 test cases passed. Status: Accepted Runtime: 47 ms Submitted: 0 minutes ago

class Solution {
public:
    int bestRotation(vector<int>& A) {
        int gain = 0;
        int r;
        priority_queue<int, vector<int>, greater<int>> q;
        for (int i = 0; i < A.size(); i++) {
            int diff = i - A[i];
            if (diff >= 0) {
                gain++;
                q.push(diff);
            }
        }
        int current = gain;
        r = 0;
        for (int shift = 1; shift <= A.size() - 1; shift++) {
            while (!q.empty() && (shift > q.top())) {
                q.pop();
                current--;
            }
            if (A[shift - 1] <= (A.size() - 1)) {
                current++;
                q.push(shift + (A.size() - 1) - A[shift - 1]);
            }
            if (current > gain) {
                r = shift;
                gain = current;
            }
        }
        return r;
    }
};

2nd version

class Solution {
public:
    int bestRotation(vector<int>& A) {
        int r = 0;
        int sz = A.size();
        vector<int> gain(A.size() + 1/*idx = [0, sz]*/, 1);
        for (int i = 0; i < sz; i++) {
            int diff = i - A[i]; /*from [-1, sz -1]*/
            if (diff >= 0) {
                gain[diff + 1]--;
            }
            if (i + 1 < A[i]) {
                gain[(sz - (A[i] - (i + 1)))]--;
            }
        }

        r = 0;
        int best = 0;
        int now = best;
        for (int i = 1; i < sz; i++) {
            now = now + gain[i];
            if (now > best) {
                best = now;
                r = i;
            }
        }
        return r;
    }
};

Diff: