Hard
题目描述
给定一个数组 nums，你可以执行以下操作任意次数：
- 选择
nums中和最小的相邻对。如果存在多个这样的对，选择最左边的一个。 - 用它们的和替换这一对。
返回使数组变为非递减所需的最小操作次数。
如果数组的每个元素都大于或等于其前一个元素（如果存在），则称该数组为非递减的。
示例 1：
输入：nums = [5,2,3,1]
输出：2
解释：
- 对 (3,1) 的和最小为 4。替换后，nums = [5,2,4]。
- 对 (2,4) 的和最小为 6。替换后，nums = [5,6]。
数组 nums 在两次操作后变为非递减。
示例 2：
输入：nums = [1,2,2]
输出：2
解释：
数组 nums 已经是有序的。
约束条件：
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
解题思路
这道题需要模拟合并相邻元素的过程，直到数组变成非递减序列。核心思路如下：
算法思路：
- 使用优先队列（最小堆）维护所有相邻对的和及其位置信息
- 使用双向链表或映射表维护当前数组的索引关系，便于快速找到相邻元素
- 使用集合记录已被删除的索引
具体步骤：
- 初始化时将所有相邻对加入优先队列
- 每次取出和最小的相邻对进行合并操作
- 合并后更新数据结构：删除旧的相邻对，添加新的相邻对
- 重复直到无法继续合并或数组已有序
关键点：
- 需要高效地找到下一个/上一个未删除的元素
- 合并操作后要及时更新优先队列中的相邻对信息
- 检查数组是否已经有序可以提前终止
这个问题的难点在于需要同时维护多个数据结构的一致性，确保在元素合并过程中能够正确追踪相邻关系。
代码实现
class Solution {
public:
int minimumPairRemoval(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return 0;
// Check if already sorted
bool sorted = true;
for (int i = 1; i < n; i++) {
if (nums[i] < nums[i-1]) {
sorted = false;
break;
}
}
if (sorted) return 0;
// Priority queue: {sum, left_index, right_index}
priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;
// Map to track next and previous indices
map<int, int> next, prev;
set<int> removed;
// Initialize
for (int i = 0; i < n; i++) {
if (i > 0) prev[i] = i - 1;
if (i < n - 1) next[i] = i + 1;
}
// Add all adjacent pairs to priority queue
for (int i = 0; i < n - 1; i++) {
pq.push({(long long)nums[i] + nums[i+1], i, i+1});
}
int operations = 0;
while (!pq.empty()) {
auto [sum, left, right] = pq.top();
pq.pop();
// Skip if indices are removed or not adjacent anymore
if (removed.count(left) || removed.count(right)) continue;
if (next.count(left) == 0 || next[left] != right) continue;
// Perform merge
operations++;
nums[left] = sum;
removed.insert(right);
// Update next/prev relationships
if (next.count(right)) {
next[left] = next[right];
prev[next[right]] = left;
next.erase(right);
} else {
next.erase(left);
}
if (prev.count(right)) {
prev.erase(right);
}
// Add new adjacent pairs
if (prev.count(left)) {
int prevIdx = prev[left];
pq.push({(long long)nums[prevIdx] + nums[left], prevIdx, left});
}
if (next.count(left)) {
int nextIdx = next[left];
pq.push({(long long)nums[left] + nums[nextIdx], left, nextIdx});
}
// Check if array is now sorted
bool isSorted = true;
int lastIdx = -1;
for (int i = 0; i < n; i++) {
if (!removed.count(i)) {
if (lastIdx != -1 && nums[i] < nums[lastIdx]) {
isSorted = false;
break;
}
lastIdx = i;
}
}
if (isSorted) break;
}
return operations;
}
};
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return 0
# Check if already sorted
if all(nums[i] >= nums[i-1] for i in range(1, n)):
return 0
import heapq
# Priority queue: [sum, left_index, right_index]
pq = []
# Track next and previous indices
next_idx = {}
prev_idx = {}
removed = set()
# Initialize
for i in range(n):
if i > 0:
prev_idx[i] = i - 1
if i < n - 1:
next_idx[i] = i + 1
# Add all adjacent pairs to priority queue
for i in range(n - 1):
heapq.heappush(pq, [nums[i] + nums[i+1], i, i+1])
operations = 0
while pq:
sum_val, left, right = heapq.heappop(pq)
# Skip if indices are removed or not adjacent anymore
if left in removed or right in removed:
continue
if left not in next_idx or next_idx[left] != right:
continue
# Perform merge
operations += 1
nums[left] = sum_val
removed.add(right)
# Update next/prev relationships
if right in next_idx:
next_idx[left] = next_idx[right]
prev_idx[next_idx[right]] = left
del next_idx[right]
else:
if left in next_idx:
del next_idx[left]
if right in prev_idx:
del prev_idx[right]
# Add new adjacent pairs
if left in prev_idx:
prev_i = prev_idx[left]
heapq.heappush(pq, [nums[prev_i] + nums[left], prev_i, left])
if left in next_idx:
next_i = next_idx[left]
heapq.heappush(pq, [nums[left] + nums[next_i], left, next_i])
# Check if array is now sorted
active_indices = [i for i in range(n) if i not in removed]
if all(nums[active_indices[i]] >= nums[active_indices[i-1]]
for i in range(1, len(active_indices))):
break
return operations
public class Solution {
public int MinimumPairRemoval(int[] nums) {
int n = nums.Length;
if (n <= 1) return 0;
// Check if already sorted
bool sorted = true;
for (int i = 1; i < n; i++) {
if (nums[i] < nums[i-1]) {
sorted = false;
break;
}
}
if (sorted) return 0;
// Priority queue: (sum, left_index, right_index)
var pq = new SortedSet<(long sum, int left, int right)>();
// Map to track next and previous indices
var next = new Dictionary<int, int>();
var prev = new Dictionary<int, int>();
var removed = new HashSet<int>();
// Initialize
for (int i = 0; i < n; i++) {
if (i > 0) prev[i] = i - 1;
if (i < n - 1) next[i] = i + 1;
}
// Add all adjacent pairs to priority queue
for (int i = 0; i < n - 1; i++) {
pq.Add(((long)nums[i] + nums[i+1], i, i+1));
}
int operations = 0;
while (pq.Count > 0) {
var (sum, left, right) = pq.Min;
pq.Remove(pq.Min);
// Skip if indices are removed or not adjacent anymore
if (removed.Contains(left) || removed.Contains(right)) continue;
if (!next.ContainsKey(left) || next[left] != right) continue;
// Perform merge
operations++;
nums[left] = (int)sum;
removed.Add(right);
// Update next/prev relationships
if (next.ContainsKey(right)) {
next[left] = next[right];
prev[next[right]] = left;
next.Remove(right);
} else {
next.Remove(left);
}
if (prev.ContainsKey(right)) {
prev.Remove(right);
}
// Add new adjacent pairs
if (prev.ContainsKey(left)) {
int prevIdx = prev[left];
pq.Add(((long)nums[prevIdx] + nums[left], prevIdx, left));
}
if (next.ContainsKey(left)) {
int nextIdx = next[left];
pq.Add(((long)nums[left] + nums[nextIdx], left, nextIdx));
}
// Check if array is now sorted
var activeIndices = new List<int>();
for (int i = 0; i < n; i++) {
if (!removed.Contains(i)) {
activeIndices.Add(i);
}
}
bool isSorted = true;
for (int i = 1; i < activeIndices.Count; i++) {
if (nums[activeIndices[i]] < nums[activeIndices[i-1]]) {
isSorted = false;
break;
}
}
if (isSorted) break;
}
return operations;
}
}
var minimumPairRemoval = function(nums) {
const n = nums.length;
if (n <= 1) return 0;
// Check if already sorted
let sorted = true;
for (let i = 1; i < n; i++) {
if (nums[i] < nums[i-1]) {
sorted = false;
break;
}
}
if (sorted) return 0;
// Priority queue using array and manual sorting
const pq = [];
// Map to track next and previous indices
const next = new Map();
const prev = new Map();
const removed = new Set();
// Initialize
for (let i = 0; i < n; i++) {
if (i > 0) prev.set(i, i - 1);
if (i < n - 1) next.set(i, i + 1);
}
// Add all adjacent pairs to priority queue
for (let i = 0; i < n - 1; i++) {
pq.push([nums[i] + nums[i+1], i, i+1]);
}
let operations = 0;
while (pq.length > 0) {
// Sort to get minimum
pq.sort((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
return a[1] - b[1]; // tie-break by left index
});
const [sum, left, right] = pq.shift();
// Skip if indices are removed or not adjacent anymore
if (removed.has(left) || removed.has(right)) continue;
if (!next.has(left) || next.get(left) !== right) continue;
// Perform merge
operations++;
nums[left] = sum;
removed.add(right);
// Update next/prev relationships
if (next.has(right)) {
next.set(left, next.get(right));
prev.set(next.get(right), left);
next.delete(right);
} else {
next.delete(left);
}
if (prev.has(right)) {
prev.delete(right);
}
// Add new adjacent pairs
if (prev.has(left)) {
const prevIdx = prev.get(left);
pq.push([nums[prevIdx] + nums[left], prevIdx, left]);
}
if (next.has(left)) {
const nextIdx = next.get(left);
pq.push([nums[left] + nums[nextIdx], left, nextIdx]);
}
// Check if array is now sorted
const activeIndices = [];
for (let i = 0; i < n; i++) {
if (!removed.has(i)) {
activeIndices.push(i);
}
}
let isSorted = true;
for (let i = 1; i < activeIndices.length; i++) {
if (nums[activeIndices[i]] < nums[activeIndices[i-1]]) {
isSorted = false;
break;
}
}
if (isSorted) break;
}
return operations;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n² log n)，其中 n 是数组长度。最坏情况下需要进行 n-1 次合并操作，每次操作涉及优先队列的插入和删除，复杂度为 O(log n)，同时需要检查数组是否有序 |
| 空间复杂度 | O(n)，用于存储优 |