)
3507: 移除最小数对使数组有序Ⅰ
思路1：小数据范围 暴力模拟
class Solution { public: int minimumPairRemoval(vector<int>& nums) { int n=nums.size(),ans=0,ap=0; bool flag=false; while(!flag){ flag=true; for(int i=1;i<n;i++){ if(nums[i]<nums[i-1]){ flag=false; break; } } if(flag==true && ap==0) return 0; ap++; if(!flag){ int min=INT_MAX,index=0; for(int i=1;i<n;i++){ int sum=nums[i]+nums[i-1]; if(sum<min){ min=sum; index=i-1; } } nums[index]=min; nums.erase(nums.begin()+index+1); n--; ans++; } else return ans; } return ans; } };为了快速模拟题目的操作，我们需要维护三种信息：
- 把相邻元素和 s，以及相邻元素中的左边元素的下标i，组成一个 pair (s,i)。我们需要添加 pair、删除 pair 以及查询这些 pair 的最小值（双关键字比较），这可以用有序集合，或者懒删除堆。
- 维护剩余下标。我们需要查询每个下标 i 左侧最近剩余下标，以及右侧最近剩余下标。这可以用有序集合，或者两个并查集，或者双向链表。（用数组模拟）
- 在相邻元素中，满足「左边元素大于右边元素」（递减）的个数，记作 dec。
不断模拟操作，直到 dec=0。
题目说「用它们的和替换这对元素」，设操作的这对元素的下标为 i 和 nxt，操作相当于把 nums[i] 增加 nums[nxt]，然后删除 nums[nxt]。
在这个过程中，dec 如何变化？
设操作的这对元素的下标为 i 和 nxt，i 左侧最近剩余下标为 pre，nxt 右侧最近剩余下标为 nxt2。操作会影响 nums[i] 和 nums[nxt]，也会影响周边相邻元素的大小关系。所以每次操作，我们需要重新考察 4 个元素值的大小关系，其下标从左到右为 pre,i,nxt,nxt2。
- 删除 nums[nxt]。如果删除前 nums[i]>nums[nxt]，把 dec 减一。
- 如果删除前 nums[pre]>nums[i]，把 dec 减一。如果删除后 nums[pre]>s，把 dec 加一。这里 s 表示操作的这对元素之和，也就是新的 nums[i] 的值。
- 如果删除前 nums[nxt]>nums[nxt2]，把 dec 减一。删除后 i 和 nxt2相邻，如果删除后 s>nums[nxt2]，把 dec 加一。
上述过程中，同时维护（添加删除）新旧相邻元素和以及下标。
思路2：懒删除堆+数组模拟双向链表
- 用最小堆（懒删除堆）代替维护 pair 的有序集合。
- 用双向链表代替维护下标的有序集合。进一步地，可以用两个数组模拟双向链表的 prev 指针和 next 指针。
- 如果堆顶下标 i 被删除，或者 i 右边下标 nxt 被删除，或者堆顶元素和不等于 nums[i]+nums[nxt]，则弹出堆顶。
vector<int> left(n+1),right(n); ranges::iota(left,-1); //值域：-1, 0, 1, 2, ..., n-1 ranges::iota(right,1); //值域：1, 2, 3, ..., nvector<long long> a(nums.begin(),nums.end());right[pq.top().second]>=n || pq.top().first!=a[pq.top().second]+a[right[pq.top().second]]这一长串判断是“懒删除”的经典写法，出现在堆/优先队列里，用来跳过那些已经失效（被合并过或移动过）的元素。
int l=left[nxt],r=right[nxt]; right[l]=r; //模拟双向链表的删除操作 left[r]=l; right[nxt]=n; //满足懒删除条件这三行就是在用双向链表的方式把节点nxt从当前链里“逻辑删除”，而并不真的挪动数组元素。链表里再也遍历不到nxt，相当于把它“跳过”了；后续代码只要看到right[i] >= n（懒删除条件）就知道i已被删。
class Solution { public: int minimumPairRemoval(vector<int>& nums) { int n=nums.size(); //小根堆(相邻元素和，左边那个数的下标) priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> pq; int dec=0; //递减的相邻对的个数 for(int i=0;i<n-1;i++){ int x=nums[i],y=nums[i+1]; if(x>y) dec++; pq.emplace(x+y,i); } //每个下标的左右最近的未删除下标(映射) vector<int> left(n+1),right(n); ranges::iota(left,-1); //值域：-1, 0, 1, 2, ..., n-1 ranges::iota(right,1); //值域：1, 2, 3, ..., n vector<long long> a(nums.begin(),nums.end()); int ans=0; while(dec){ ans++; //如果堆顶数据与实际数据不符，说明堆顶数据是之前本应删除，但没有删除的数据（懒删除） while(right[pq.top().second]>=n || pq.top().first!=a[pq.top().second]+a[right[pq.top().second]]){ pq.pop(); } auto[s,i]=pq.top(); pq.pop(); //删除相邻元素和最小的一对 //(当前元素，下一个数) int nxt=right[i]; dec-=a[i]>a[nxt]; //旧数据 //(前一个数，当前元素) int pre=left[i]; if(pre>=0){ dec-=a[pre]>a[i]; //旧数据 dec+=a[pre]>s; //新数据 pq.emplace(a[pre]+s,pre); } //(下一个数，下下一个数) int nxt2=right[nxt]; if(nxt2<n){ dec-=a[nxt]>a[nxt2]; //旧数据 dec+=s>a[nxt2]; //新数据（当前元素，下下一个数） pq.emplace(s+a[nxt2],i);//nxt被删除了 } a[i]=s; //删除 nxt int l=left[nxt],r=right[nxt]; right[l]=r; //模拟双向链表的删除操作 left[r]=l; right[nxt]=n; //满足懒删除条件 } return ans; } };
