Leetcode 2163. Minimum difference of sum after element deletion

I'll give you a subscript from 0  The starting array of integers  nums , It contains  3 * n  Elements .

You can start your nums  Delete in just  n  Elements , The rest 2 * n  The elements will be divided into two Same size   Part of .

front  n  The first element belongs to the first part , Their sum is recorded as  sumfirst .
Back  n  The first element belongs to the second part , Their sum is recorded as  sumsecond .
The sum of two parts Difference value   Write it down as  sumfirst - sumsecond .

For example ,sumfirst = 3 And  sumsecond = 2 , Their difference is  1 .
Let's take another example ,sumfirst = 2 And  sumsecond = 3 , Their difference is  -1 .
Please go back and delete n  After elements , The remaining two parts and The minimum value of the difference   How much is the .

Example 1：

Input ：nums = [3,1,2]
Output ：-1
explain ：nums Yes 3 Elements , therefore n = 1 .
So we need to nums Delete in 1 Elements , And divide the remaining elements into two parts .
- If we delete nums[0] = 3 , The array becomes [1,2] . The difference between the sum of the two parts is 1 - 2 = -1 .
- If we delete nums[1] = 1 , The array becomes [3,2] . The difference between the sum of the two parts is 3 - 2 = 1 .
- If we delete nums[2] = 2 , The array becomes [3,1] . The difference between the sum of the two parts is 3 - 1 = 2 .
The minimum difference between the sum of two parts is min(-1,1,2) = -1 .
Example 2：

Input ：nums = [7,9,5,8,1,3]
Output ：1
explain ：n = 2 . So we need to delete 2 Elements , And divide the remaining elements into 2 part .
If we delete the element nums[2] = 5 and nums[3] = 8 , The remaining elements are [7,9,1,3] . The difference between and is (7+9) - (1+3) = 12 .
In order to get the minimum difference , We should delete nums[1] = 9 and nums[4] = 1 , The remaining elements are [7,5,8,3] . The difference between and is (7+5) - (8+3) = 1 .
Observation can be seen , The best answer is 1 .
 

Tips ：

nums.length == 3 * n
1 <= n <= 105
1 <= nums[i] <= 105

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-difference-in-sums-after-removal-of-elements
 

solution ：

Priority queue + The prefix and . Read the prompt and then write it out , How to solve this problem sumfisrt-sumsecond The difference is the smallest , It should be sumfirst As small as possible ,sumsecond As big as possible , about sumfirst[i] Before presentation i Of the elements n Minimum value of sum of numbers , about sumsecond[i] similar , It's just from the back to the front , For maximum . We can use the priority queue to find n The maximum number .

class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        using ll = long long;
        priority_queue<ll, vector<ll>, less<ll>> pq;// The operation of the priority queue is similar to that of the stack 
        int n3 = nums.size();
        vector<ll> lSum(n3);
        int n = n3 / 3;
        ll sum = 0;
        for (int i = 0; i < 2 * n; ++i)
        {
            if (i < n)
            {
                sum += nums[i];
                pq.push(nums[i]);
            }  
            else 
            {
                if (nums[i] < pq.top())
                {
                    sum -= pq.top();
                    pq.pop();
                    pq.push(nums[i]);
                    sum += nums[i];
                }
            }
            lSum[i] = sum;
        }
        priority_queue<ll, vector<ll>, greater<ll>> pq2;
        sum = 0;
        ll ans = 1e18;
        for (int i = n3 - 1; i >= n; --i)
        {
            if (i >= 2 * n)
            {
                sum += nums[i];
                pq2.push(nums[i]);
            }
            else 
            {
                if(nums[i] > pq2.top())
                {
                    sum -= pq2.top();
                    pq2.pop();
                    pq2.push(nums[i]);
                    sum += nums[i];
                }
            }
            if( i <= 2 * n)
                ans = min(ans, lSum[i - 1] - sum);
        }
        return ans;
    }
};