problem:LCP 24. 数字游戏

code

c++

class Solution {
public:
    vector<int> numsGame(vector<int>& nums) {
        const int mod = 1000000007;
        // 默认是大根堆
        priority_queue<int, vector<int>> left;
        // 小根堆
        priority_queue<int, vector<int>, greater<int>> right;
        vector<int> ans(nums.size());  
        long long leftsum=0,rightsum =0;
        for (int i = 0; i < nums.size(); i++) {
            int b = nums[i]-i;
            // 偶数
            if (i % 2 == 0) {
                if( right.size()==0 || right.size()>0 && b<right.top()){
                    left.push(b);
                    leftsum+=b;
                }
                else if(b>=right.top())  {
                    right.push(b);
                    left.push(right.top());
                    leftsum+=right.top();
                    rightsum+=b-right.top();
                    right.pop();
                }
                int top = left.top();
                // 如果从头到尾依次更改O(n)复杂度，这里维护leftsum和rightsum
                ans[i] = (rightsum - leftsum + top)%mod;
            }
            // 奇数
            else {
                left.push(b);
                right.push(left.top());
                rightsum += left.top();
                leftsum+=b-left.top();
                left.pop();
                int top = left.top();
                ans[i] = (rightsum-leftsum)%mod;
            }
        }
        return ans;
    }
};