(nice!!!)(LeetCode 每日一题) 2163. 删除元素后和的最小差值 （贪心+优先队列）

思路：贪心+优先队列，时间复杂度0(nlogn)。

将数组nums分成两段，前半段选出最小的n个元素，后半段选出最大的n个元素即可。分段的位置可以在[n,2n-1]。
用优先队列从右到左，预先处理出后半段每个分段点的最大值，细节看注释。
C++版本：

class Solution {
public:typedef long long LL;long long minimumDifference(vector<int>& nums) {int m=nums.size();int n=m/3;// 优先队列，保留后半段最大的n个数，所以采用小顶堆priority_queue<int,vector<int>,greater<>> qu2(nums.end()-n,nums.end());LL sum=reduce(nums.end()-n,nums.end(),0LL);// 记录每个分段点，后半段的最大值vector<LL> v(m);v[m-n]=sum;//从右到左，预先处理出后半段每个分段点的最大值for(int i=m-n-1;i>=n;i--){if(nums[i]>qu2.top()){sum-=qu2.top();qu2.pop();qu2.push(nums[i]);sum+=nums[i];}v[i]=sum;}// 优先队列，保留前半段最小的n个数，所以采用大顶堆priority_queue<int> qu1(nums.begin(),nums.begin()+n);sum=reduce(nums.begin(),nums.begin()+n,0LL);// 答案LL mn=sum-v[m-2*n];// 从左到右，维护前半段最小的n个元素for(int i=n;i<m-n;i++){if(nums[i]<qu1.top()){sum-=qu1.top();qu1.pop();qu1.push(nums[i]);sum+=nums[i];}//维护最小值mn=min(mn,sum-v[i+1]);}return mn;}
};