给你一个数组 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]
输出： 0
解释：
数组 nums 已经是非递减的。
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109Problem: 3510. 移除最小数对使数组有序 II
[TOC]
先不管是否为递增数组，当作一道新题目，每次操作选择相邻的最小和。然后合并
要获取最小的相邻值，那就用最小堆，两个相邻值合并相当于区间合并，用area来模拟区间合并：
# 区间合并后，当前 i 的区间范围，-inf 即为被合并了
area = [ (i,i) for i in range(n) ]
并初始化堆，堆中包含三个值：
for i in range(n-1):
heappush(heap,(nums[i]+nums[i+1],i,i+1))
模拟合并的代码：
while True:
while heap:
num,l,r = heap[0]
if area[l][1] + 1 != r or nums[l] + nums[r] != num:
heappop(heap)
else:
break
# 合并完了
if not heap:
break
# 操作
num,l,r = heappop(heap)
# 两个区间
a,b = area[l]
x,y = area[r]
# 求和合并
nums[a] = num
nums[y] = num
# 区间合并
area[b] = area[x] = (-inf,-inf)
area[a] = (a,y)
area[y] = (a,y)
# 和前后区间合并并入堆
if y + 1 < n and area[y+1][0] != -inf:
heappush(heap,(num + nums[y+1],l,y+1))
if a - 1 >= 0 and area[a-1][0] != -inf:
heappush(heap,(num + nums[area[a-1][0]],area[a-1][0],l))
现在考虑判断每次操作后，合并后的数组是否递增：
看到区间修改和区间查询，应该要想到线段树了
一般出现区间修改都考虑lazy线段树，但这题不需要，因为每次被合并的区间都不会再对该区间中的子区间进行操作，也就是不会有lazy标记下放了，所以不需要lazy标记
f[k] 中维护三个值：
# 真实值，是否递增，区间左侧值，区间右侧值
self.f = [[False,-1,-1] for _ in range(4*n)]
这个合并不难：
def pushup(self,lp,rp):
lf,a,b = lp
rf,x,y = rp
if not lf or not rf:
return (False,-1,-1)
if b <= x:
return (True,a,y)
else:
return (False,-1,-1)
最后就是在第一步模拟操作时加入 区间修改和区间查询 ，以及操作数统计就好了。
更多题目模板总结，请参考2024年度总结与题目分享
###Python3
# 标记不下放版本
class SegmentTree:
def __init__(self,nums):
n = len(nums)
self.nums = nums
# 真实值，是否递增，区间左侧值，区间右侧值
self.f = [[False,-1,-1] for _ in range(4*n)]
self.buildTree(1,0,n-1)
self.n = n
def pushup(self,lp,rp):
lf,a,b = lp
rf,x,y = rp
if not lf or not rf:
return (False,-1,-1)
if b <= x:
return (True,a,y)
else:
return (False,-1,-1)
# 初始化，求区间和
def buildTree(self,k,l,r):
# 叶子节点
if l == r:
self.f[k] = (True,self.nums[l],self.nums[l])
return
mid = (l+r)//2
self.buildTree(2*k,l,mid)
self.buildTree(2*k+1,mid+1,r)
# 每个k掌管 [2*k,2*k+1]
self.f[k] = self.pushup(self.f[2*k],self.f[2*k+1])
def update(self,start,end,x):
return self._update(1,0,self.n-1,start,end,x)
def _update(self,k,l,r,start,end,x):
# 序号为k的点，掌管范围是l～r， 在区间start～end上，
# 待更新区间刚好等于当前标准区间，则直接更新
if l == start and r == end:
# 肯定递增
self.f[k] = [True,x,x]
return
mid = (l+r)//2
if end <= mid: # 只在左子树
self._update(2*k,l,mid,start,end,x)
# 注意这里的return
elif start > mid: # 只在右子树
self._update(2*k+1,mid+1,r,start,end,x)
else:
# 否则对左右子树都需要处理
self._update(2*k, l, mid, start,mid,x)
self._update(2*k+1,mid+1,r, mid+1,end,x)
# 后缀数组更新，左右子树更新后更新当前子树
self.f[k] = self.pushup(self.f[2*k],self.f[2*k+1])
def query(self):
return self.f[1][0]
# 范围内含有1的个数
def _query(self,k,l,r,start,end):
# update时对于标准区间已经更新，返回即可
if l == start and r == end: # 叶子节点
return self.f[k]
mid = (l+r)//2
# 需要更新，标记下放
if not self.v[k]:
self._update(2*k,l,mid,l,mid)
self._update(2*k+1,mid+1,r,mid+1,r)
self.v[k] = True
if end <= mid:
return self._query(2*k,l,mid,start,end) # 注意这里的p已经加上了v[k]的影响
elif start > mid:
return self._query(2*k+1,mid+1,r,start,end)
leftPart = self._query(2*k,l,mid,start,mid)
rightPart = self._query(2*k+1,mid+1,r,mid+1,end)
return leftPart + rightPart
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
'''
相邻和最小的 a,b
a = a + b
移除b
非递减
1e5
线段树
nums[i] nums[j] 合并的话
相当于
区间修改 把区间 [i,j] 换成相同的值为 nums[i] + nums[j]
区间查询 查询整个区间是否递增
那就是线段树
快速找最小：
堆 + 并查集模拟删除
'''
n = len(nums)
# 值，区间 [l,r] 两端点相加
heap = []
# 区间合并后，当前 i 的区间范围，-inf 即为被合并了
area = [ (i,i) for i in range(n) ]
for i in range(n-1):
heappush(heap,(nums[i]+nums[i+1],i,i+1))
tree = SegmentTree(nums)
res = 0
while not tree.query():
res += 1
while heap:
num,l,r = heap[0]
if area[l][1] + 1 != r or nums[l] + nums[r] != num:
heappop(heap)
else:
break
# 操作
num,l,r = heappop(heap)
# 两个区间
a,b = area[l]
x,y = area[r]
# 求和合并
nums[a] = num
nums[y] = num
tree.update(a,y,num)
# 区间合并
area[b] = area[x] = (-inf,-inf)
area[a] = (a,y)
area[y] = (a,y)
# 和前后区间合并并入堆
if y + 1 < n and area[y+1][0] != -inf:
heappush(heap,(num + nums[y+1],l,y+1))
if a - 1 >= 0 and area[a-1][0] != -inf:
heappush(heap,(num + nums[area[a-1][0]],area[a-1][0],l))
return res
为了快速模拟题目的操作，我们需要维护三种信息：
不断模拟操作，直到 $\textit{dec} = 0$。
题目说「用它们的和替换这对元素」，设操作的这对元素的下标为 $i$ 和 $\textit{nxt}$，操作相当于把 $\textit{nums}[i]$ 增加 $\textit{nums}[\textit{nxt}]$，然后删除 $\textit{nums}[\textit{nxt}]$。
在这个过程中，$\textit{dec}$ 如何变化？
设操作的这对元素的下标为 $i$ 和 $\textit{nxt}$，$i$ 左侧最近剩余下标为 $\textit{pre}$，$\textit{nxt}$ 右侧最近剩余下标为 $\textit{nxt}_2$。
操作会影响 $\textit{nums}[i]$ 和 $\textit{nums}[\textit{nxt}]$，也会影响周边相邻元素的大小关系。所以每次操作，我们需要重新考察 $4$ 个元素值的大小关系，下标从左到右为 $\textit{pre},i,\textit{nxt},\textit{nxt}_2$。
上述过程中，同时维护（添加删除）新旧相邻元素和以及下标。
本题视频讲解，欢迎点赞关注~
###py
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
sl = SortedList() # (相邻元素和，左边那个数的下标)
idx = SortedList(range(len(nums))) # 剩余下标
dec = 0 # 递减的相邻对的个数
for i, (x, y) in enumerate(pairwise(nums)):
if x > y:
dec += 1
sl.add((x + y, i))
ans = 0
while dec > 0:
ans += 1
s, i = sl.pop(0) # 删除相邻元素和最小的一对
k = idx.bisect_left(i)
# (当前元素，下一个数)
nxt = idx[k + 1]
if nums[i] > nums[nxt]: # 旧数据
dec -= 1
# (前一个数，当前元素)
if k > 0:
pre = idx[k - 1]
if nums[pre] > nums[i]: # 旧数据
dec -= 1
if nums[pre] > s: # 新数据
dec += 1
sl.remove((nums[pre] + nums[i], pre))
sl.add((nums[pre] + s, pre))
# (下一个数，下下一个数)
if k + 2 < len(idx):
nxt2 = idx[k + 2]
if nums[nxt] > nums[nxt2]: # 旧数据
dec -= 1
if s > nums[nxt2]: # 新数据（当前元素，下下一个数）
dec += 1
sl.remove((nums[nxt] + nums[nxt2], nxt))
sl.add((s + nums[nxt2], i))
nums[i] = s # 把 nums[nxt] 加到 nums[i] 中
idx.remove(nxt) # 删除 nxt
return ans
###java
class Solution {
private record Pair(long s, int i) {
}
public int minimumPairRemoval(int[] nums) {
int n = nums.length;
// (相邻元素和，左边那个数的下标)
TreeSet<Pair> pairs = new TreeSet<>((a, b) -> a.s != b.s ? Long.compare(a.s, b.s) : a.i - b.i);
int dec = 0; // 递减的相邻对的个数
for (int i = 0; i < n - 1; i++) {
int x = nums[i];
int y = nums[i + 1];
if (x > y) {
dec++;
}
pairs.add(new Pair(x + y, i));
}
// 剩余下标
TreeSet<Integer> idx = new TreeSet<>();
for (int i = 0; i < n; i++) {
idx.add(i);
}
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nums[i];
}
int ans = 0;
while (dec > 0) {
ans++;
// 删除相邻元素和最小的一对
Pair p = pairs.pollFirst();
long s = p.s;
int i = p.i;
// (当前元素，下一个数)
int nxt = idx.higher(i);
if (a[i] > a[nxt]) { // 旧数据
dec--;
}
// (前一个数，当前元素)
Integer pre = idx.lower(i);
if (pre != null) {
if (a[pre] > a[i]) { // 旧数据
dec--;
}
if (a[pre] > s) { // 新数据
dec++;
}
pairs.remove(new Pair(a[pre] + a[i], pre));
pairs.add(new Pair(a[pre] + s, pre));
}
// (下一个数，下下一个数)
Integer nxt2 = idx.higher(nxt);
if (nxt2 != null) {
if (a[nxt] > a[nxt2]) { // 旧数据
dec--;
}
if (s > a[nxt2]) { // 新数据（当前元素，下下一个数）
dec++;
}
pairs.remove(new Pair(a[nxt] + a[nxt2], nxt));
pairs.add(new Pair(s + a[nxt2], i));
}
a[i] = s; // 把 a[nxt] 加到 a[i] 中
idx.remove(nxt); // 删除 nxt
}
return ans;
}
}
###cpp
class Solution {
public:
int minimumPairRemoval(vector<int>& nums) {
int n = nums.size();
set<pair<long long, int>> pairs; // (相邻元素和，左边那个数的下标)
int dec = 0; // 递减的相邻对的个数
for (int i = 0; i + 1 < n; i++) {
int x = nums[i], y = nums[i + 1];
if (x > y) {
dec++;
}
pairs.emplace(x + y, i);
}
set<int> idx; // 剩余下标
for (int i = 0; i < n; i++) {
idx.insert(i);
}
vector<long long> a(nums.begin(), nums.end());
int ans = 0;
while (dec > 0) {
ans++;
// 删除相邻元素和最小的一对
auto [s, i] = *pairs.begin();
pairs.erase(pairs.begin());
auto it = idx.lower_bound(i);
// (当前元素，下一个数)
auto nxt_it = next(it);
int nxt = *nxt_it;
dec -= a[i] > a[nxt]; // 旧数据
// (前一个数，当前元素)
if (it != idx.begin()) {
int pre = *prev(it);
dec -= a[pre] > a[i]; // 旧数据
dec += a[pre] > s; // 新数据
pairs.erase({a[pre] + a[i], pre});
pairs.emplace(a[pre] + s, pre);
}
// (下一个数，下下一个数)
auto nxt2_it = next(nxt_it);
if (nxt2_it != idx.end()) {
int nxt2 = *nxt2_it;
dec -= a[nxt] > a[nxt2]; // 旧数据
dec += s > a[nxt2]; // 新数据（当前元素，下下一个数）
pairs.erase({a[nxt] + a[nxt2], nxt});
pairs.emplace(s + a[nxt2], i);
}
a[i] = s; // 把 a[nxt] 加到 a[i] 中
idx.erase(nxt); // 删除 nxt
}
return ans;
}
};
###go
// import "github.com/emirpasic/gods/v2/trees/redblacktree"
func minimumPairRemoval(nums []int) (ans int) {
n := len(nums)
type pair struct{ s, i int }
// (相邻元素和，左边那个数的下标)
pairs := redblacktree.NewWith[pair, struct{}](func(a, b pair) int { return cmp.Or(a.s-b.s, a.i-b.i) })
dec := 0 // 递减的相邻对的个数
for i := range n - 1 {
x, y := nums[i], nums[i+1]
if x > y {
dec++
}
pairs.Put(pair{x + y, i}, struct{}{})
}
// 剩余下标
idx := redblacktree.New[int, struct{}]()
for i := range n {
idx.Put(i, struct{}{})
}
for dec > 0 {
ans++
it := pairs.Left()
s := it.Key.s
i := it.Key.i
pairs.Remove(it.Key) // 删除相邻元素和最小的一对
// (当前元素，下一个数)
node, _ := idx.Ceiling(i + 1)
nxt := node.Key
if nums[i] > nums[nxt] { // 旧数据
dec--
}
// (前一个数，当前元素)
node, _ = idx.Floor(i - 1)
if node != nil {
pre := node.Key
if nums[pre] > nums[i] { // 旧数据
dec--
}
if nums[pre] > s { // 新数据
dec++
}
pairs.Remove(pair{nums[pre] + nums[i], pre})
pairs.Put(pair{nums[pre] + s, pre}, struct{}{})
}
// (下一个数，下下一个数)
node, _ = idx.Ceiling(nxt + 1)
if node != nil {
nxt2 := node.Key
if nums[nxt] > nums[nxt2] { // 旧数据
dec--
}
if s > nums[nxt2] { // 新数据（当前元素，下下一个数）
dec++
}
pairs.Remove(pair{nums[nxt] + nums[nxt2], nxt})
pairs.Put(pair{s + nums[nxt2], i}, struct{}{})
}
nums[i] = s // 把 nums[nxt] 加到 nums[i] 中
idx.Remove(nxt) // 删除 nxt
}
return
}
用最小堆（懒删除堆）代替维护 pair 的有序集合。
用双向链表代替维护下标的有序集合。进一步地，可以用两个数组模拟双向链表的 $\textit{prev}$ 指针和 $\textit{next}$ 指针。
如果堆顶下标 $i$ 被删除，或者 $i$ 右边下标 $\textit{nxt}$ 被删除，或者堆顶元素和不等于 $\textit{nums}[i]+\textit{nums}[\textit{nxt}]$，则弹出堆顶。
###py
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
n = len(nums)
h = [] # (相邻元素和，左边那个数的下标)
dec = 0 # 递减的相邻对的个数
for i, (x, y) in enumerate(pairwise(nums)):
if x > y:
dec += 1
h.append((x + y, i))
heapify(h)
lazy = defaultdict(int)
# 每个下标的左右最近的未删除下标
left = list(range(-1, n)) # 加一个哨兵，防止下标越界
right = list(range(1, n + 1))
ans = 0
while dec:
ans += 1
while lazy[h[0]]:
lazy[heappop(h)] -= 1
s, i = heappop(h) # 删除相邻元素和最小的一对
# (当前元素，下一个数)
nxt = right[i]
if nums[i] > nums[nxt]: # 旧数据
dec -= 1
# (前一个数，当前元素)
pre = left[i]
if pre >= 0:
if nums[pre] > nums[i]: # 旧数据
dec -= 1
if nums[pre] > s: # 新数据
dec += 1
lazy[(nums[pre] + nums[i], pre)] += 1 # 懒删除
heappush(h, (nums[pre] + s, pre))
# (下一个数，下下一个数)
nxt2 = right[nxt]
if nxt2 < n:
if nums[nxt] > nums[nxt2]: # 旧数据
dec -= 1
if s > nums[nxt2]: # 新数据（当前元素，下下一个数）
dec += 1
lazy[(nums[nxt] + nums[nxt2], nxt)] += 1 # 懒删除
heappush(h, (s + nums[nxt2], i))
nums[i] = s
# 删除 nxt
l, r = left[nxt], right[nxt]
right[l] = r # 模拟双向链表的删除操作
left[r] = l
return ans
###py
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
n = len(nums)
h = [] # (相邻元素和，左边那个数的下标)
dec = 0 # 递减的相邻对的个数
for i, (x, y) in enumerate(pairwise(nums)):
if x > y:
dec += 1
h.append((x + y, i))
heapify(h)
# 每个下标的左右最近的未删除下标
left = list(range(-1, n)) # 加一个哨兵，防止下标越界
right = list(range(1, n + 1)) # 注意最下面的代码，删除 nxt 的时候额外把 right[nxt] 置为 n
ans = 0
while dec:
ans += 1
# 如果堆顶数据与实际数据不符，说明堆顶数据是之前本应删除，但没有删除的数据（懒删除）
while right[h[0][1]] >= n or h[0][0] != nums[h[0][1]] + nums[right[h[0][1]]]:
heappop(h)
s, i = heappop(h) # 删除相邻元素和最小的一对
# (当前元素，下一个数)
nxt = right[i]
if nums[i] > nums[nxt]: # 旧数据
dec -= 1
# (前一个数，当前元素)
pre = left[i]
if pre >= 0:
if nums[pre] > nums[i]: # 旧数据
dec -= 1
if nums[pre] > s: # 新数据
dec += 1
heappush(h, (nums[pre] + s, pre))
# (下一个数，下下一个数)
nxt2 = right[nxt]
if nxt2 < n:
if nums[nxt] > nums[nxt2]: # 旧数据
dec -= 1
if s > nums[nxt2]: # 新数据（当前元素，下下一个数）
dec += 1
heappush(h, (s + nums[nxt2], i))
nums[i] = s
# 删除 nxt
l, r = left[nxt], right[nxt]
right[l] = r # 模拟双向链表的删除操作
left[r] = l
right[nxt] = n # 表示删除 nxt
return ans
###java
class Solution {
private record Pair(long s, int i) {
}
public int minimumPairRemoval(int[] nums) {
int n = nums.length;
// (相邻元素和，左边那个数的下标)
PriorityQueue<Pair> h = new PriorityQueue<>((a, b) -> a.s != b.s ? Long.compare(a.s, b.s) : a.i - b.i);
int dec = 0; // 递减的相邻对的个数
for (int i = 0; i < n - 1; i++) {
int x = nums[i];
int y = nums[i + 1];
if (x > y) {
dec++;
}
h.offer(new Pair(x + y, i));
}
// 每个下标的左右最近的未删除下标
int[] left = new int[n + 1];
int[] right = new int[n + 1];
for (int i = 0; i <= n; i++) {
left[i] = i - 1;
right[i] = i + 1;
}
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nums[i];
}
int ans = 0;
while (dec > 0) {
ans++;
// 如果堆顶数据与实际数据不符，说明堆顶数据是之前本应删除，但没有删除的数据（懒删除）
while (right[h.peek().i] >= n || h.peek().s != a[h.peek().i] + a[right[h.peek().i]]) {
h.poll();
}
// 删除相邻元素和最小的一对
Pair p = h.poll();
long s = p.s;
int i = p.i;
// (当前元素，下一个数)
int nxt = right[i];
if (a[i] > a[nxt]) { // 旧数据
dec--;
}
// (前一个数，当前元素)
int pre = left[i];
if (pre >= 0) {
if (a[pre] > a[i]) { // 旧数据
dec--;
}
if (a[pre] > s) { // 新数据
dec++;
}
h.offer(new Pair(a[pre] + s, pre));
}
// (下一个数，下下一个数)
int nxt2 = right[nxt];
if (nxt2 < n) {
if (a[nxt] > a[nxt2]) { // 旧数据
dec--;
}
if (s > a[nxt2]) { // 新数据（当前元素，下下一个数）
dec++;
}
h.add(new Pair(s + a[nxt2], i));
}
a[i] = s; // 把 a[nxt] 加到 a[i] 中
// 删除 nxt
int l = left[nxt];
int r = right[nxt];
right[l] = r; // 模拟双向链表的删除操作
left[r] = l;
right[nxt] = n; // 表示删除 nxt
}
return ans;
}
}
###cpp
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 + 1 < n; 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);
ranges::iota(right, 1);
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);
}
a[i] = s;
// 删除 nxt
int l = left[nxt], r = right[nxt];
right[l] = r; // 模拟双向链表的删除操作
left[r] = l;
right[nxt] = n; // 表示删除 nxt
}
return ans;
}
};
###go
func minimumPairRemoval(nums []int) (ans int) {
n := len(nums)
h := make(hp, n-1)
dec := 0 // 递减的相邻对的个数
for i := range n - 1 {
x, y := nums[i], nums[i+1]
if x > y {
dec++
}
h[i] = pair{x + y, i}
}
heap.Init(&h)
lazy := map[pair]int{}
// 每个下标的左右最近的未删除下标
left := make([]int, n+1) // 加一个哨兵，防止下标越界
right := make([]int, n)
for i := range n {
left[i] = i - 1
right[i] = i + 1
}
remove := func(i int) {
l, r := left[i], right[i]
right[l] = r // 模拟双向链表的删除操作
left[r] = l
}
for dec > 0 {
ans++
for lazy[h[0]] > 0 {
lazy[h[0]]--
heap.Pop(&h)
}
p := heap.Pop(&h).(pair) // 删除相邻元素和最小的一对
s := p.s
i := p.i
// (当前元素，下一个数)
nxt := right[i]
if nums[i] > nums[nxt] { // 旧数据
dec--
}
// (前一个数，当前元素)
pre := left[i]
if pre >= 0 {
if nums[pre] > nums[i] { // 旧数据
dec--
}
if nums[pre] > s { // 新数据
dec++
}
lazy[pair{nums[pre] + nums[i], pre}]++ // 懒删除
heap.Push(&h, pair{nums[pre] + s, pre})
}
// (下一个数，下下一个数)
nxt2 := right[nxt]
if nxt2 < n {
if nums[nxt] > nums[nxt2] { // 旧数据
dec--
}
if s > nums[nxt2] { // 新数据（当前元素，下下一个数）
dec++
}
lazy[pair{nums[nxt] + nums[nxt2], nxt}]++ // 懒删除
heap.Push(&h, pair{s + nums[nxt2], i})
}
nums[i] = s
remove(nxt)
}
return
}
type pair struct{ s, i int } // (相邻元素和，左边那个数的下标)
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { a, b := h[i], h[j]; return a.s < b.s || a.s == b.s && a.i < b.i }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
###go
func minimumPairRemoval(nums []int) (ans int) {
n := len(nums)
h := make(hp, n-1)
dec := 0 // 递减的相邻对的个数
for i := range n - 1 {
x, y := nums[i], nums[i+1]
if x > y {
dec++
}
h[i] = pair{x + y, i}
}
heap.Init(&h)
// 每个下标的左右最近的未删除下标
left := make([]int, n+1) // 加一个哨兵，防止下标越界
right := make([]int, n)
for i := range n {
left[i] = i - 1
right[i] = i + 1
}
remove := func(i int) {
l, r := left[i], right[i]
right[l] = r // 模拟双向链表的删除操作
left[r] = l
right[i] = n // 表示 i 已被删除
}
for dec > 0 {
ans++
// 如果堆顶数据与实际数据不符，说明堆顶数据是之前本应删除，但没有删除的数据（懒删除）
for right[h[0].i] >= n || nums[h[0].i]+nums[right[h[0].i]] != h[0].s {
heap.Pop(&h)
}
p := heap.Pop(&h).(pair) // 删除相邻元素和最小的一对
s := p.s
i := p.i
// (当前元素，下一个数)
nxt := right[i]
if nums[i] > nums[nxt] { // 旧数据
dec--
}
// (前一个数，当前元素)
pre := left[i]
if pre >= 0 {
if nums[pre] > nums[i] { // 旧数据
dec--
}
if nums[pre] > s { // 新数据
dec++
}
heap.Push(&h, pair{nums[pre] + s, pre})
}
// (下一个数，下下一个数)
nxt2 := right[nxt]
if nxt2 < n {
if nums[nxt] > nums[nxt2] { // 旧数据
dec--
}
if s > nums[nxt2] { // 新数据（当前元素，下下一个数）
dec++
}
heap.Push(&h, pair{s + nums[nxt2], i})
}
nums[i] = s
remove(nxt)
}
return
}
type pair struct{ s, i int } // (相邻元素和，左边那个数的下标)
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { a, b := h[i], h[j]; return a.s < b.s || a.s == b.s && a.i < b.i }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
欢迎关注 B站@灵茶山艾府
思路与算法
由于数据范围非常小，故直接按题意模拟即可。
遍历 $\textit{nums}$ 的相邻元素，维护最小相邻数对和的同时判断 $\textit{nums}$ 是否满足非严格单调递增，如果不满足条件则更新数组，将相邻数对合并为新元素。重复以上操作，直到满足非严格单调递增的条件或 $\textit{nums}$ 的长度为 $1$ 为止。
代码
###C++
class Solution {
public:
int minimumPairRemoval(std::vector<int>& nums) {
int count = 0;
while (nums.size() > 1) {
bool isAscending = true;
int minSum = std::numeric_limits<int>::max();
int targetIndex = -1;
for (size_t i = 0; i < nums.size() - 1; ++i) {
int sum = nums[i] + nums[i + 1];
if (nums[i] > nums[i + 1]) {
isAscending = false;
}
if (sum < minSum) {
minSum = sum;
targetIndex = static_cast<int>(i);
}
}
if (isAscending) {
break;
}
count++;
nums[targetIndex] = minSum;
nums.erase(nums.begin() + targetIndex + 1);
}
return count;
}
};
###Java
class Solution {
public int minimumPairRemoval(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int num : nums) {
list.add(num);
}
var count = 0;
while (list.size() > 1) {
var isAscending = true;
var minSum = Integer.MAX_VALUE;
var targetIndex = -1;
for (var i = 0; i < list.size() - 1; i++) {
var sum = list.get(i) + list.get(i + 1);
if (list.get(i) > list.get(i + 1)) {
isAscending = false;
}
if (sum < minSum) {
minSum = sum;
targetIndex = i;
}
}
if (isAscending) {
break;
}
count++;
list.set(targetIndex, minSum);
list.remove(targetIndex + 1);
}
return count;
}
}
###Python
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
count = 0
while len(nums) > 1:
isAscending = True
minSum = float("inf")
targetIndex = -1
for i in range(len(nums) - 1):
pair_sum = nums[i] + nums[i + 1]
if nums[i] > nums[i + 1]:
isAscending = False
if pair_sum < minSum:
minSum = pair_sum
targetIndex = i
if isAscending:
break
count += 1
nums[targetIndex] = minSum
nums.pop(targetIndex + 1)
return count
###C#
public class Solution {
public int MinimumPairRemoval(int[] nums) {
var count = 0;
var list = nums.ToList();
while (list.Count > 1) {
var isAscending = true;
var minSum = int.MaxValue;
var targetIndex = -1;
for (var i = 0; i < list.Count - 1; i++) {
var sum = list[i] + list[i + 1];
if (list[i] > list[i + 1]) {
isAscending = false;
}
if (sum < minSum) {
minSum = sum;
targetIndex = i;
}
}
if (isAscending) {
break;
}
count++;
list[targetIndex] = minSum;
list.RemoveAt(targetIndex + 1);
}
return count;
}
}
###JavaScript
var minimumPairRemoval = function (nums) {
let count = 0;
while (nums.length > 1) {
let isAscending = true;
let minSum = Infinity;
let targetIndex = -1;
for (let i = 0; i < nums.length - 1; i++) {
const sum = nums[i] + nums[i + 1];
if (nums[i] > nums[i + 1]) {
isAscending = false;
}
if (sum < minSum) {
minSum = sum;
targetIndex = i;
}
}
if (isAscending) {
break;
}
count++;
nums[targetIndex] = minSum;
nums.splice(targetIndex + 1, 1);
}
return count;
}
###TypeScript
function minimumPairRemoval(nums: number[]): number {
let count = 0;
while (nums.length > 1) {
let isAscending = true;
let minSum = Infinity;
let targetIndex = -1;
for (let i = 0; i < nums.length - 1; i++) {
const sum = nums[i] + nums[i + 1];
if (nums[i] > nums[i + 1]) {
isAscending = false;
}
if (sum < minSum) {
minSum = sum;
targetIndex = i;
}
}
if (isAscending) {
break;
}
count++;
nums[targetIndex] = minSum;
nums.splice(targetIndex + 1, 1);
}
return count;
}
###Go
func minimumPairRemoval(nums []int) int {
count := 0
for len(nums) > 1 {
isAscending := true
minSum := 1 << 31 - 1
targetIndex := -1
for i := 0; i < len(nums)-1; i++ {
sum := nums[i] + nums[i+1]
if nums[i] > nums[i+1] {
isAscending = false
}
if sum < minSum {
minSum = sum
targetIndex = i
}
}
if isAscending {
break
}
count++
nums[targetIndex] = minSum
nums = append(nums[:targetIndex+1], nums[targetIndex + 2:]...)
}
return count
}
###C
int minimumPairRemoval(int* nums, int numsSize) {
int count = 0;
int size = numsSize;
while (size > 1) {
int isAscending = 1;
int minSum = INT_MAX;
int targetIndex = -1;
for (int i = 0; i < size - 1; i++) {
int sum = nums[i] + nums[i + 1];
if (nums[i] > nums[i + 1]) {
isAscending = 0;
}
if (sum < minSum) {
minSum = sum;
targetIndex = i;
}
}
if (isAscending) {
break;
}
count++;
nums[targetIndex] = minSum;
for (int i = targetIndex + 1; i < size - 1; i++) {
nums[i] = nums[i + 1];
}
size--;
}
return count;
}
###Rust
impl Solution {
pub fn minimum_pair_removal(nums: Vec<i32>) -> i32 {
let mut count = 0;
let mut nums = nums.clone();
while nums.len() > 1 {
let mut is_ascending = true;
let mut min_sum = i32::MAX;
let mut target_index = -1;
for i in 0..nums.len() - 1 {
let sum = nums[i] + nums[i + 1];
if nums[i] > nums[i + 1] {
is_ascending = false;
}
if sum < min_sum {
min_sum = sum;
target_index = i as i32;
}
}
if is_ascending {
break;
}
count += 1;
let ti = target_index as usize;
nums[ti] = min_sum;
nums.remove(ti + 1);
}
count
}
}
复杂度分析
时间复杂度：$O(n^2)$，其中 $n$ 是 $\textit{nums}$ 的长度。合并数对最多进行 $n$ 次；判断单调性、寻找数对和删除数组中的元素均需要消耗 $O(n)$ 的时间，故总时间复杂度为 $O(n^2)$。
空间复杂度：$O(1)$，只用到了常数个变量。
思路与算法
除了直接在数组上移除元素外，也可以采用模拟链表的思路，从而支持 $O(1)$ 的删除操作。考虑维护一个 $\textit{next}$ 数组，代表下标 $i$ 处元素的下一个元素所在位置。由于不管是判断单调性，还是寻找最小相邻数对和，都只是对线性表的顺序遍历，因此遍历部分的逻辑基本和方法一基本相同，只需要在删除元素的时候维护 $\textit{next}$ 数组，将目标元素的下一个元素指向下下个元素即可。
代码
###C++
class Solution {
public:
int minimumPairRemoval(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> next(n);
std::iota(next.begin(), next.end(), 1);
next[n - 1] = -1;
int count = 0;
while (n - count > 1) {
int curr = 0;
int target = 0;
int targetAdjSum = nums[target] + nums[next[target]];
bool isAscending = true;
while (curr != -1 && next[curr] != -1) {
if (nums[curr] > nums[next[curr]]) {
isAscending = false;
}
int currAdjSum = nums[curr] + nums[next[curr]];
if (currAdjSum < targetAdjSum) {
target = curr;
targetAdjSum = currAdjSum;
}
curr = next[curr];
}
if (isAscending) {
break;
}
count++;
next[target] = next[next[target]];
nums[target] = targetAdjSum;
}
return count;
}
};
###Java
class Solution {
public int minimumPairRemoval(int[] nums) {
var n = nums.length;
var next = new int[n];
Arrays.setAll(next, i -> i + 1);
next[n - 1] = -1;
var count = 0;
while (n - count > 1) {
var curr = 0;
var target = 0;
var targetAdjSum = nums[target] + nums[next[target]];
var isAscending = true;
while (curr != -1 && next[curr] != -1) {
if (nums[curr] > nums[next[curr]]) {
isAscending = false;
}
var currAdjSum = nums[curr] + nums[next[curr]];
if (currAdjSum < targetAdjSum) {
target = curr;
targetAdjSum = currAdjSum;
}
curr = next[curr];
}
if (isAscending) {
break;
}
count++;
next[target] = next[next[target]];
nums[target] = targetAdjSum;
}
return count;
}
}
###Python
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
next_node = list(range(1, len(nums) + 1))
next_node[-1] = None
count = 0
while len(nums) - count > 1:
curr = 0
target = 0
target_adj_sum = nums[target] + nums[next_node[target]]
is_ascending = True
while curr is not None and next_node[curr] is not None:
if nums[curr] > nums[next_node[curr]]:
is_ascending = False
curr_adj_sum = nums[curr] + nums[next_node[curr]]
if curr_adj_sum < target_adj_sum:
target = curr
target_adj_sum = curr_adj_sum
curr = next_node[curr]
if is_ascending:
break
count += 1
next_node[target] = next_node[next_node[target]]
nums[target] = target_adj_sum
return count
###C#
public class Solution {
public int MinimumPairRemoval(int[] nums) {
var next = new int?[nums.Length];
for (var i = 0; i < nums.Length - 1; i++) next[i] = i + 1;
var count = 0;
while (nums.Length - count > 1) {
int? curr = 0;
var target = 0;
var targetAdjSum = nums[target] + nums[next[target]!.Value];
var isAscending = true;
while (curr is not null && next[curr.Value] is not null) {
var nextVal = next[curr.Value]!.Value;
if (nums[curr.Value] > nums[nextVal]) {
isAscending = false;
}
var currAdjSum = nums[curr.Value] + nums[nextVal];
if (currAdjSum < targetAdjSum) {
target = curr.Value;
targetAdjSum = currAdjSum;
}
curr = next[curr.Value];
}
if (isAscending) {
break;
}
count++;
next[target] = next[next[target]!.Value];
nums[target] = targetAdjSum;
}
return count;
}
}
###JavaScript
var minimumPairRemoval = function (nums) {
const next = nums.map((_, i) => i + 1);
next[nums.length - 1] = null;
let count = 0;
while (nums.length - count > 1) {
let curr = 0;
let target = 0;
let targetAdjSum = nums[target] + nums[next[target]];
let isAscending = true;
while (curr !== null && next[curr] !== null) {
if (nums[curr] > nums[next[curr]]) {
isAscending = false;
}
let currAdjSum = nums[curr] + nums[next[curr]];
if (currAdjSum < targetAdjSum) {
target = curr;
targetAdjSum = currAdjSum;
}
curr = next[curr];
}
if (isAscending) {
break;
}
count++;
next[target] = next[next[target]];
nums[target] = targetAdjSum;
}
return count;
}
###TypeScript
function minimumPairRemoval(nums: number[]): number {
const next = nums.map<number | null>((_, i) => i + 1);
next[nums.length - 1] = null;
let count = 0;
while (nums.length - count > 1) {
let curr: number | null = 0;
let target = 0;
let targetAdjSum = nums[target] + nums[next[target]!];
let isAscending = true;
while (curr !== null && next[curr] !== null) {
if (nums[curr] > nums[next[curr]!]) {
isAscending = false;
}
let currAdjSum = nums[curr] + nums[next[curr]!];
if (currAdjSum < targetAdjSum) {
target = curr;
targetAdjSum = currAdjSum;
}
curr = next[curr];
}
if (isAscending) {
break;
}
count++;
next[target] = next[next[target]!];
nums[target] = targetAdjSum;
}
return count;
}
###Go
func minimumPairRemoval(nums []int) int {
n := len(nums)
next := make([]int, n)
for i := 0; i < n; i++ {
next[i] = i + 1
}
next[n - 1] = -1
count := 0
for n - count > 1 {
curr := 0
target := 0
targetAdjSum := nums[target] + nums[next[target]]
isAscending := true
for curr != -1 && next[curr] != -1 {
if nums[curr] > nums[next[curr]] {
isAscending = false
}
currAdjSum := nums[curr] + nums[next[curr]]
if currAdjSum < targetAdjSum {
target = curr
targetAdjSum = currAdjSum
}
curr = next[curr]
}
if isAscending {
break
}
count++
next[target] = next[next[target]]
nums[target] = targetAdjSum
}
return count
}
###C
int minimumPairRemoval(int* nums, int n) {
int* next = (int*)malloc(n * sizeof(int));
if (next == NULL) {
return -1;
}
for (int i = 0; i < n; i++) {
next[i] = i + 1;
}
next[n - 1] = -1;
int count = 0;
while (n - count > 1) {
int curr = 0;
int target = 0;
int targetAdjSum = nums[target] + nums[next[target]];
int isAscending = 1;
while (curr != -1 && next[curr] != -1) {
if (nums[curr] > nums[next[curr]]) {
isAscending = 0;
}
int currAdjSum = nums[curr] + nums[next[curr]];
if (currAdjSum < targetAdjSum) {
target = curr;
targetAdjSum = currAdjSum;
}
curr = next[curr];
}
if (isAscending) {
break;
}
count++;
next[target] = next[next[target]];
nums[target] = targetAdjSum;
}
free(next);
return count;
}
###Rust
impl Solution {
pub fn minimum_pair_removal(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut nums = nums.clone();
let mut next: Vec<isize> = (0..n as isize).map(|i| i + 1).collect();
next[n - 1] = -1;
let mut count = 0;
while (n as i32 - count) > 1 {
let mut curr: isize = 0;
let mut target: isize = 0;
let mut target_adj_sum = nums[0] + nums[next[0] as usize];
let mut is_ascending = true;
while curr != -1 && next[curr as usize] != -1 {
let curr_idx = curr as usize;
let next_idx = next[curr_idx] as usize;
if nums[curr_idx] > nums[next_idx] {
is_ascending = false;
}
let curr_adj_sum = nums[curr_idx] + nums[next_idx];
if curr_adj_sum < target_adj_sum {
target = curr;
target_adj_sum = curr_adj_sum;
}
curr = next[curr_idx];
}
if is_ascending {
break;
}
count += 1;
let target_idx = target as usize;
let next_target = next[target_idx] as usize;
next[target_idx] = next[next_target];
nums[target_idx] = target_adj_sum;
}
count
}
}
复杂度分析
时间复杂度：$O(n^2)$，其中 $n$ 是 $\textit{nums}$ 的长度。具体分析同方法一，只是删除操作此时只需 $O(1)$ 即可完成。
空间复杂度：$O(n)$，$\textit{next}$ 数组需要使用 $O(n)$ 的辅助空间。
我们定义一个函数 $\text{is_non_decreasing}(a)$，用于判断数组 $a$ 是否为非递减数组。
我们使用一个循环，直到数组 $arr$ 为非递减数组为止。在每次循环中，我们找到数组 $arr$ 中相邻元素对的和的最小值，并记录该对的左边元素的下标 $k$。然后，我们将该对的和替换左边的元素，并删除右边的元素。最后，我们返回操作的次数。
###python
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
arr = nums[:]
ans = 0
def is_non_decreasing(a: List[int]) -> bool:
for i in range(1, len(a)):
if a[i] < a[i - 1]:
return False
return True
while not is_non_decreasing(arr):
k = 0
s = arr[0] + arr[1]
for i in range(1, len(arr) - 1):
t = arr[i] + arr[i + 1]
if s > t:
s = t
k = i
arr[k] = s
arr.pop(k + 1)
ans += 1
return ans
###java
class Solution {
public int minimumPairRemoval(int[] nums) {
List<Integer> arr = new ArrayList<>();
for (int x : nums) {
arr.add(x);
}
int ans = 0;
while (!isNonDecreasing(arr)) {
int k = 0;
int s = arr.get(0) + arr.get(1);
for (int i = 1; i < arr.size() - 1; ++i) {
int t = arr.get(i) + arr.get(i + 1);
if (s > t) {
s = t;
k = i;
}
}
arr.set(k, s);
arr.remove(k + 1);
++ans;
}
return ans;
}
private boolean isNonDecreasing(List<Integer> arr) {
for (int i = 1; i < arr.size(); ++i) {
if (arr.get(i) < arr.get(i - 1)) {
return false;
}
}
return true;
}
}
###cpp
class Solution {
public:
int minimumPairRemoval(vector<int>& nums) {
vector<int> arr = nums;
int ans = 0;
while (!isNonDecreasing(arr)) {
int k = 0;
int s = arr[0] + arr[1];
for (int i = 1; i < arr.size() - 1; ++i) {
int t = arr[i] + arr[i + 1];
if (s > t) {
s = t;
k = i;
}
}
arr[k] = s;
arr.erase(arr.begin() + (k + 1));
++ans;
}
return ans;
}
private:
bool isNonDecreasing(const vector<int>& arr) {
for (int i = 1; i < (int) arr.size(); ++i) {
if (arr[i] < arr[i - 1]) {
return false;
}
}
return true;
}
};
###go
func minimumPairRemoval(nums []int) int {
arr := append([]int(nil), nums...)
ans := 0
isNonDecreasing := func(a []int) bool {
for i := 1; i < len(a); i++ {
if a[i] < a[i-1] {
return false
}
}
return true
}
for !isNonDecreasing(arr) {
k := 0
s := arr[0] + arr[1]
for i := 1; i < len(arr)-1; i++ {
t := arr[i] + arr[i+1]
if s > t {
s = t
k = i
}
}
arr[k] = s
copy(arr[k+1:], arr[k+2:])
arr = arr[:len(arr)-1]
ans++
}
return ans
}
###ts
function minimumPairRemoval(nums: number[]): number {
const arr = nums.slice();
let ans = 0;
const isNonDecreasing = (a: number[]): boolean => {
for (let i = 1; i < a.length; i++) {
if (a[i] < a[i - 1]) {
return false;
}
}
return true;
};
while (!isNonDecreasing(arr)) {
let k = 0;
let s = arr[0] + arr[1];
for (let i = 1; i < arr.length - 1; ++i) {
const t = arr[i] + arr[i + 1];
if (s > t) {
s = t;
k = i;
}
}
arr[k] = s;
arr.splice(k + 1, 1);
ans++;
}
return ans;
}
###rust
impl Solution {
pub fn minimum_pair_removal(nums: Vec<i32>) -> i32 {
let mut arr: Vec<i32> = nums.clone();
let mut ans: i32 = 0;
fn is_non_decreasing(a: &Vec<i32>) -> bool {
for i in 1..a.len() {
if a[i] < a[i - 1] {
return false;
}
}
true
}
while !is_non_decreasing(&arr) {
let mut k: usize = 0;
let mut s: i32 = arr[0] + arr[1];
for i in 1..arr.len() - 1 {
let t: i32 = arr[i] + arr[i + 1];
if s > t {
s = t;
k = i;
}
}
arr[k] = s;
arr.remove(k + 1);
ans += 1;
}
ans
}
}
时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
给你一个数组 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]
输出： 0
解释：
数组 nums 已经是非递减的。
提示：
1 <= nums.length <= 50-1000 <= nums[i] <= 1000如果初始时数组 $\textit{nums}$ 已经非递减，则最小操作次数是 $0$。以下只考虑初始时数组 $\textit{nums}$ 不满足非递减的情况。
最直观的思路是模拟数组的操作。每次操作时，遍历数组 $\textit{nums}$ 寻找相邻元素对中的元素和最小且最左边的一个元素对，用元素和替换这对元素，直到数组变成非递减，此时的操作次数即为将数组变为非递减所需的最小操作次数。
用 $n$ 表示数组 $\textit{nums}$ 的长度。由于每次操作之后都会将数组中的元素个数减少 $1$，因此每次操作应将执行合并操作的元素对右侧的元素向左移动。对于 $0 \le k < n$ 的整数 $k$，在执行 $k$ 次操作之后，剩余元素个数是 $n - k$，因此下一次操作时应只考虑数组的前 $n - k$ 个元素。
###Java
class Solution {
public int minimumPairRemoval(int[] nums) {
int removals = 0;
int n = nums.length;
while (!isNonDecreasing(nums, n)) {
update(nums, n);
removals++;
n--;
}
return removals;
}
public void update(int[] nums, int n) {
int minSum = Integer.MAX_VALUE;
int index = -1;
for (int i = 0; i < n - 1; i++) {
if (nums[i] + nums[i + 1] < minSum) {
minSum = nums[i] + nums[i + 1];
index = i;
}
}
if (index >= 0) {
nums[index] = minSum;
for (int i = index + 1; i < n - 1; i++) {
nums[i] = nums[i + 1];
}
}
}
public boolean isNonDecreasing(int[] nums, int n) {
for (int i = 1; i < n; i++) {
if (nums[i - 1] > nums[i]) {
return false;
}
}
return true;
}
}
###C#
public class Solution {
public int MinimumPairRemoval(int[] nums) {
int removals = 0;
int n = nums.Length;
while (!IsNonDecreasing(nums, n)) {
Update(nums, n);
removals++;
n--;
}
return removals;
}
public void Update(int[] nums, int n) {
int minSum = int.MaxValue;
int index = -1;
for (int i = 0; i < n - 1; i++) {
if (nums[i] + nums[i + 1] < minSum) {
minSum = nums[i] + nums[i + 1];
index = i;
}
}
if (index >= 0) {
nums[index] = minSum;
for (int i = index + 1; i < n - 1; i++) {
nums[i] = nums[i + 1];
}
}
}
public bool IsNonDecreasing(int[] nums, int n) {
for (int i = 1; i < n; i++) {
if (nums[i - 1] > nums[i]) {
return false;
}
}
return true;
}
}
时间复杂度：$O(n^2)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。最差情况需要执行 $n - 1$ 次操作，每次操作的时间是 $O(n)$，因此时间复杂度是 $O(n^2)$。
空间复杂度：$O(1)$。所有的操作均为原地修改数组。
使用双向链表、哈希表和优先队列，可以将时间复杂度降低到 $O(n \log n)$。具体见题解「3510. 移除最小数对使数组有序 II」。
###Java
class Solution {
private class Node {
private int index;
private long value;
private Node prev;
private Node next;
public Node() {
this(-1, Integer.MAX_VALUE);
}
public Node(int index, long value) {
this.index = index;
this.value = value;
prev = null;
next = null;
}
public int getIndex() {
return index;
}
public long getValue() {
return value;
}
public void setValue(long value) {
this.value = value;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public int minimumPairRemoval(int[] nums) {
int removals = 0;
Map<Integer, Node> indexToNode = new HashMap<Integer, Node>();
Node pseudoHead = new Node();
Node pseudoTail = new Node();
Node prevNode = pseudoHead;
int n = nums.length;
for (int i = 0; i < n; i++) {
Node node = new Node(i, nums[i]);
indexToNode.put(i, node);
prevNode.setNext(node);
node.setPrev(prevNode);
prevNode = node;
}
prevNode.setNext(pseudoTail);
pseudoTail.setPrev(prevNode);
PriorityQueue<long[]> pq = new PriorityQueue<long[]>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
int reversePairs = 0;
for (int i = 0; i < n - 1; i++) {
pq.offer(new long[]{nums[i] + nums[i + 1], i, i + 1});
if (nums[i] > nums[i + 1]) {
reversePairs++;
}
}
while (reversePairs > 0) {
long[] arr = pq.poll();
long newValue = arr[0];
int index1 = (int) arr[1], index2 = (int) arr[2];
if (!indexToNode.containsKey(index1) || !indexToNode.containsKey(index2) || newValue != indexToNode.get(index1).getValue() + indexToNode.get(index2).getValue()) {
continue;
}
removals++;
Node node1 = indexToNode.get(index1), node2 = indexToNode.get(index2);
if (node1.getValue() > node2.getValue()) {
reversePairs--;
}
if (node1.getPrev().getIndex() >= 0 && node1.getPrev().getValue() > node1.getValue()) {
reversePairs--;
}
if (node2.getNext().getIndex() >= 0 && node2.getNext().getValue() < node2.getValue()) {
reversePairs--;
}
node1.setValue(newValue);
remove(node2);
indexToNode.remove(index2);
if (node1.getPrev().getIndex() >= 0) {
pq.offer(new long[]{node1.getPrev().getValue() + node1.getValue(), node1.getPrev().getIndex(), node1.getIndex()});
if (node1.getPrev().getValue() > node1.getValue()) {
reversePairs++;
}
}
if (node1.getNext().getIndex() >= 0) {
pq.offer(new long[]{node1.getValue() + node1.getNext().getValue(), node1.getIndex(), node1.getNext().getIndex()});
if (node1.getNext().getValue() < node1.getValue()) {
reversePairs++;
}
}
}
return removals;
}
public void remove(Node node) {
Node prev = node.getPrev(), next = node.getNext();
prev.setNext(next);
next.setPrev(prev);
}
}
###C#
public class Solution {
public class Node {
public int Index { get; set; }
public long Value { get; set; }
public Node Prev { get; set; }
public Node Next { get; set; }
public Node() : this(-1, int.MaxValue) {
}
public Node(int index, long value) {
Index = index;
Value = value;
Prev = null;
Next = null;
}
}
public int MinimumPairRemoval(int[] nums) {
int removals = 0;
IDictionary<int, Node> indexToNode = new Dictionary<int, Node>();
Node pseudoHead = new Node();
Node pseudoTail = new Node();
Node prevNode = pseudoHead;
int n = nums.Length;
for (int i = 0; i < n; i++) {
Node node = new Node(i, nums[i]);
indexToNode.Add(i, node);
prevNode.Next = node;
node.Prev = prevNode;
prevNode = node;
}
prevNode.Next = pseudoTail;
pseudoTail.Prev = prevNode;
Comparer<Tuple<long, int, int>> comparer = Comparer<Tuple<long, int, int>>.Create((a, b) => a.Item1 != b.Item1 ? a.Item1.CompareTo(b.Item1) : a.Item2.CompareTo(b.Item2));
PriorityQueue<Tuple<long, int, int>, Tuple<long, int, int>> pq = new PriorityQueue<Tuple<long, int, int>, Tuple<long, int, int>>(comparer);
int reversePairs = 0;
for (int i = 0; i < n - 1; i++) {
pq.Enqueue(new Tuple<long, int, int>(nums[i] + nums[i + 1], i, i + 1), new Tuple<long, int, int>(nums[i] + nums[i + 1], i, i + 1));
if (nums[i] > nums[i + 1]) {
reversePairs++;
}
}
while (reversePairs > 0) {
Tuple<long, int, int> tuple = pq.Dequeue();
long newValue = tuple.Item1;
int index1 = tuple.Item2, index2 = tuple.Item3;
if (!indexToNode.ContainsKey(index1) || !indexToNode.ContainsKey(index2) || newValue != indexToNode[index1].Value + indexToNode[index2].Value) {
continue;
}
removals++;
Node node1 = indexToNode[index1], node2 = indexToNode[index2];
if (node1.Value > node2.Value) {
reversePairs--;
}
if (node1.Prev.Index >= 0 && node1.Prev.Value > node1.Value) {
reversePairs--;
}
if (node2.Next.Index >= 0 && node2.Next.Value < node2.Value) {
reversePairs--;
}
node1.Value = newValue;
Remove(node2);
indexToNode.Remove(index2);
if (node1.Prev.Index >= 0) {
pq.Enqueue(new Tuple<long, int, int>(node1.Prev.Value + node1.Value, node1.Prev.Index, node1.Index), new Tuple<long, int, int>(node1.Prev.Value + node1.Value, node1.Prev.Index, node1.Index));
if (node1.Prev.Value > node1.Value) {
reversePairs++;
}
}
if (node1.Next.Index >= 0) {
pq.Enqueue(new Tuple<long, int, int>(node1.Value + node1.Next.Value, node1.Index, node1.Next.Index), new Tuple<long, int, int>(node1.Value + node1.Next.Value, node1.Index, node1.Next.Index));
if (node1.Next.Value < node1.Value) {
reversePairs++;
}
}
}
return removals;
}
public void Remove(Node node) {
Node prev = node.Prev, next = node.Next;
prev.Next = next;
next.Prev = prev;
}
}
时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。遍历数组初始化数据结构的时间是 $O(n \log n)$，最差情况需要执行 $n - 1$ 次操作，每次操作中的双向链表和哈希表的更新时间是 $O(1)$，优先队列的更新时间是 $O(\log n)$，因此时间复杂度是 $O(n \log n)$。
空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。双向链表、哈希表和优先队列的空间是 $O(n)$。
对于一个整数 $a$，满足 $a \lor (a + 1)$ 的结果一定为奇数，因此，如果 $\text{nums[i]}$ 是偶数，那么 $\text{ans}[i]$ 一定不存在，直接返回 $-1$。本题中 $\textit{nums}[i]$ 是质数，判断是否是偶数，只需要判断是否等于 $2$ 即可。
如果 $\text{nums[i]}$ 是奇数，假设 $\text{nums[i]} = \text{0b1101101}$，由于 $a \lor (a + 1) = \text{nums[i]}$，等价于将 $a$ 的最后一个为 $0$ 的二进制位变为 $1$。那么求解 $a$，就等价于将 $\text{nums[i]}$ 的最后一个 $0$ 的下一位 $1$ 变为 $0$。我们只需要从低位（下标为 $1$）开始遍历，找到第一个为 $0$ 的二进制位，如果是第 $i$ 位，那么我们就将 $\text{nums[i]}$ 的第 $i - 1$ 位变为 $1$，即 $\text{ans}[i] = \text{nums[i]} \oplus 2^{i - 1}$。
遍历所有的 $\text{nums[i]}$，即可得到答案。
###python
class Solution:
def minBitwiseArray(self, nums: List[int]) -> List[int]:
ans = []
for x in nums:
if x == 2:
ans.append(-1)
else:
for i in range(1, 32):
if x >> i & 1 ^ 1:
ans.append(x ^ 1 << (i - 1))
break
return ans
###java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int n = nums.size();
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int x = nums.get(i);
if (x == 2) {
ans[i] = -1;
} else {
for (int j = 1; j < 32; ++j) {
if ((x >> j & 1) == 0) {
ans[i] = x ^ 1 << (j - 1);
break;
}
}
}
}
return ans;
}
}
###cpp
class Solution {
public:
vector<int> minBitwiseArray(vector<int>& nums) {
vector<int> ans;
for (int x : nums) {
if (x == 2) {
ans.push_back(-1);
} else {
for (int i = 1; i < 32; ++i) {
if (x >> i & 1 ^ 1) {
ans.push_back(x ^ 1 << (i - 1));
break;
}
}
}
}
return ans;
}
};
###go
func minBitwiseArray(nums []int) (ans []int) {
for _, x := range nums {
if x == 2 {
ans = append(ans, -1)
} else {
for i := 1; i < 32; i++ {
if x>>i&1 == 0 {
ans = append(ans, x^1<<(i-1))
break
}
}
}
}
return
}
###ts
function minBitwiseArray(nums: number[]): number[] {
const ans: number[] = [];
for (const x of nums) {
if (x === 2) {
ans.push(-1);
} else {
for (let i = 1; i < 32; ++i) {
if (((x >> i) & 1) ^ 1) {
ans.push(x ^ (1 << (i - 1)));
break;
}
}
}
}
return ans;
}
时间复杂度 $O(n \times \log M)$，其中 $n$ 和 $M$ 分别是数组 $\text{nums}$ 的长度和数组中的最大值。忽略答案数组的空间消耗，空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
给你一个长度为 n 的 质数 数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下 条件 均成立：
ans[i] OR (ans[i] + 1) == nums[i]除此以外，你需要 最小化 结果数组里每一个 ans[i] 。
如果没法找到符合 条件 的 ans[i] ，那么 ans[i] = -1 。
质数 指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。
示例 1：
输入：nums = [2,3,5,7]
输出：[-1,1,4,3]
解释：
i = 0 ，不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ，所以 ans[0] = -1 。i = 1 ，满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ，因为 1 OR (1 + 1) = 3 。i = 2 ，满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ，因为 4 OR (4 + 1) = 5 。i = 3 ，满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ，因为 3 OR (3 + 1) = 7 。示例 2：
输入：nums = [11,13,31]
输出：[9,12,15]
解释：
i = 0 ，满足 ans[0] OR (ans[0] + 1) = 11 的最小 ans[0] 为 9 ，因为 9 OR (9 + 1) = 11 。i = 1 ，满足 ans[1] OR (ans[1] + 1) = 13 的最小 ans[1] 为 12 ，因为 12 OR (12 + 1) = 13 。i = 2 ，满足 ans[2] OR (ans[2] + 1) = 31 的最小 ans[2] 为 15 ，因为 15 OR (15 + 1) = 31 。
提示：
1 <= nums.length <= 1002 <= nums[i] <= 109nums[i] 是一个质数。例如 $x=100111$，那么 $x\ |\ (x+1) = 100111\ |\ 101000 = 101111$。
可以发现，$x\ |\ (x+1)$ 的本质是把二进制最右边的 $0$ 置为 $1$。
反过来，如果已知 $x\ |\ (x+1) = 101111$，那么倒推 $x$，需要把 $101111$ 中的某个 $1$ 变成 $0$。满足要求的 $x$ 有：
$$
\begin{aligned}
100111 \
101011 \
101101 \
101110 \
\end{aligned}
$$
其中最小的是 $100111$，也就是把 $101111$ 最右边的 $0$ 的右边的 $1$ 置为 $0$。
无解的情况：由于 $x\ |\ (x+1)$ 最低位一定是 $1$（因为 $x$ 和 $x+1$ 中必有一奇数），所以如果 $\textit{nums}[i]$ 是偶数（质数中只有 $2$），那么无解。
举例说明：把 $101111$ 取反，得 $010000$，其 $\text{lowbit}=10000$，右移一位得 $1000$。把 $101111$ 与 $1000$ 异或，即可得到 $100111$。
关于 $\text{lowbit}$ 的原理，请看 从集合论到位运算，常见位运算技巧分类总结！
本题视频讲解，欢迎点赞关注~
###py
class Solution:
def minBitwiseArray(self, nums: List[int]) -> List[int]:
for i, x in enumerate(nums):
if x == 2:
nums[i] = -1
else:
t = ~x
nums[i] ^= (t & -t) >> 1
return nums
###java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int n = nums.size();
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
int x = nums.get(i);
if (x == 2) {
ans[i] = -1;
} else {
int t = ~x;
int lowbit = t & -t;
ans[i] = x ^ (lowbit >> 1);
}
}
return ans;
}
}
###cpp
class Solution {
public:
vector<int> minBitwiseArray(vector<int>& nums) {
for (int& x : nums) { // 注意这里是引用
if (x == 2) {
x = -1;
} else {
int t = ~x;
x ^= (t & -t) >> 1;
}
}
return nums;
}
};
###go
func minBitwiseArray(nums []int) []int {
for i, x := range nums {
if x == 2 {
nums[i] = -1
} else {
t := ^x
nums[i] ^= t & -t >> 1
}
}
return nums
}
把 $101111$ 加一，得到 $110000$，再 AND $101111$ 取反后的值 $010000$，可以得到方法一中的 $\text{lowbit}=10000$。
###py
class Solution:
def minBitwiseArray(self, nums: List[int]) -> List[int]:
for i, x in enumerate(nums):
if x == 2:
nums[i] = -1
else:
nums[i] ^= ((x + 1) & ~x) >> 1
return nums
###java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int n = nums.size();
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
int x = nums.get(i);
if (x == 2) {
ans[i] = -1;
} else {
int lowbit = (x + 1) & ~x;
ans[i] = x ^ (lowbit >> 1);
}
}
return ans;
}
}
###cpp
class Solution {
public:
vector<int> minBitwiseArray(vector<int>& nums) {
for (int& x : nums) { // 注意这里是引用
if (x == 2) {
x = -1;
} else {
x ^= ((x + 1) & ~x) >> 1;
}
}
return nums;
}
};
###go
func minBitwiseArray(nums []int) []int {
for i, x := range nums {
if x == 2 {
nums[i] = -1
} else {
nums[i] ^= (x + 1) &^ x >> 1
}
}
return nums
}
见下面位运算题单的「八、思维题」。
欢迎关注 B站@灵茶山艾府
对于一个整数 $a$，满足 $a \lor (a + 1)$ 的结果一定为奇数，因此，如果 $\text{nums[i]}$ 是偶数，那么 $\text{ans}[i]$ 一定不存在，直接返回 $-1$。本题中 $\textit{nums}[i]$ 是质数，判断是否是偶数，只需要判断是否等于 $2$ 即可。
如果 $\text{nums[i]}$ 是奇数，假设 $\text{nums[i]} = \text{0b1101101}$，由于 $a \lor (a + 1) = \text{nums[i]}$，等价于将 $a$ 的最后一个为 $0$ 的二进制位变为 $1$。那么求解 $a$，就等价于将 $\text{nums[i]}$ 的最后一个 $0$ 的下一位 $1$ 变为 $0$。我们只需要从低位（下标为 $1$）开始遍历，找到第一个为 $0$ 的二进制位，如果是第 $i$ 位，那么我们就将 $\text{nums[i]}$ 的第 $i - 1$ 位变为 $1$，即 $\text{ans}[i] = \text{nums[i]} \oplus 2^{i - 1}$。
遍历所有的 $\text{nums[i]}$，即可得到答案。
###python
class Solution:
def minBitwiseArray(self, nums: List[int]) -> List[int]:
ans = []
for x in nums:
if x == 2:
ans.append(-1)
else:
for i in range(1, 32):
if x >> i & 1 ^ 1:
ans.append(x ^ 1 << (i - 1))
break
return ans
###java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int n = nums.size();
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int x = nums.get(i);
if (x == 2) {
ans[i] = -1;
} else {
for (int j = 1; j < 32; ++j) {
if ((x >> j & 1) == 0) {
ans[i] = x ^ 1 << (j - 1);
break;
}
}
}
}
return ans;
}
}
###cpp
class Solution {
public:
vector<int> minBitwiseArray(vector<int>& nums) {
vector<int> ans;
for (int x : nums) {
if (x == 2) {
ans.push_back(-1);
} else {
for (int i = 1; i < 32; ++i) {
if (x >> i & 1 ^ 1) {
ans.push_back(x ^ 1 << (i - 1));
break;
}
}
}
}
return ans;
}
};
###go
func minBitwiseArray(nums []int) (ans []int) {
for _, x := range nums {
if x == 2 {
ans = append(ans, -1)
} else {
for i := 1; i < 32; i++ {
if x>>i&1 == 0 {
ans = append(ans, x^1<<(i-1))
break
}
}
}
}
return
}
###ts
function minBitwiseArray(nums: number[]): number[] {
const ans: number[] = [];
for (const x of nums) {
if (x === 2) {
ans.push(-1);
} else {
for (let i = 1; i < 32; ++i) {
if (((x >> i) & 1) ^ 1) {
ans.push(x ^ (1 << (i - 1)));
break;
}
}
}
}
return ans;
}
时间复杂度 $O(n \times \log M)$，其中 $n$ 和 $M$ 分别是数组 $\text{nums}$ 的长度和数组中的最大值。忽略答案数组的空间消耗，空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下 条件 均成立：
ans[i] OR (ans[i] + 1) == nums[i]除此以外，你需要 最小化 结果数组里每一个 ans[i] 。
如果没法找到符合 条件 的 ans[i] ，那么 ans[i] = -1 。
质数 指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。
示例 1：
输入：nums = [2,3,5,7]
输出：[-1,1,4,3]
解释：
i = 0 ，不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ，所以 ans[0] = -1 。i = 1 ，满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ，因为 1 OR (1 + 1) = 3 。i = 2 ，满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ，因为 4 OR (4 + 1) = 5 。i = 3 ，满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ，因为 3 OR (3 + 1) = 7 。示例 2：
输入：nums = [11,13,31]
输出：[9,12,15]
解释：
i = 0 ，满足 ans[0] OR (ans[0] + 1) = 11 的最小 ans[0] 为 9 ，因为 9 OR (9 + 1) = 11 。i = 1 ，满足 ans[1] OR (ans[1] + 1) = 13 的最小 ans[1] 为 12 ，因为 12 OR (12 + 1) = 13 。i = 2 ，满足 ans[2] OR (ans[2] + 1) = 31 的最小 ans[2] 为 15 ，因为 15 OR (15 + 1) = 31 。
提示：
1 <= nums.length <= 1002 <= nums[i] <= 1000nums[i] 是一个质数。数组 $\textit{nums}$ 的长度是 $n$。对于 $0 \le i < n$ 的每个下标 $i$，满足 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) = \textit{nums}[i]$。由于 $\textit{nums}[i]$ 是质数，即 $\textit{nums}[i]$ 至少等于 $2$，因此 $\textit{ans}[i]$ 一定是正整数。
最直观的计算 $\textit{ans}[i]$ 的方法是从小到大遍历每个正整数 $x$，寻找满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$ 的最小正整数 $x$ 填入 $\textit{ans}[i]$，如果不存在符合要求的正整数 $x$ 则 $\textit{ans}[i] = -1$。
根据按位或运算的性质，必有 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) \ge \textit{ans}[i]$，因此当 $\textit{ans}[i] > \textit{nums}[i]$ 时必有 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) > \textit{nums}[i]$，计算 $\textit{ans}[i]$ 时只需要遍历不超过 $\textit{nums}[i]$ 的值。
###Java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int n = nums.size();
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = find(nums.get(i));
}
return ans;
}
public int find(int num) {
for (int i = 1; i <= num; i++) {
if ((i | (i + 1)) == num) {
return i;
}
}
return -1;
}
}
###C#
public class Solution {
public int[] MinBitwiseArray(IList<int> nums) {
int n = nums.Count;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = Find(nums[i]);
}
return ans;
}
public int Find(int num) {
for (int i = 1; i <= num; i++) {
if ((i | (i + 1)) == num) {
return i;
}
}
return -1;
}
}
时间复杂度：$O(nm)$，其中 $n$ 是数组 $\textit{nums}$ 的长度，$m$ 是数组 $\textit{nums}$ 中的最大元素。答案数组中的每个元素的计算时间都是 $O(m)$。
空间复杂度：$O(1)$。注意返回值不计入空间复杂度。
当存在正整数 $x$ 满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$ 时，由于 $x$ 和 $x + 1$ 当中一定有一个奇数，因此 $\textit{nums}[i]$ 一定是奇数。如果 $\textit{nums}[i]$ 是偶数，则不存在符合要求的 $x$，对应 $\textit{ans}[i] = -1$。当 $\textit{nums}[i]$ 是奇数时，可以取 $x = \textit{nums}[i] - 1$，则满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$，因此如果 $\textit{nums}[i]$ 是奇数，则一定存在符合要求的 $x$。
由于 $\textit{nums}[i]$ 是质数，唯一的偶质数是 $2$，因此当 $\textit{nums}[i] = 2$ 时 $\textit{ans}[i] = -1$。当 $\textit{nums}[i] > 2$ 时 $\textit{ans}[i] > 0$，需要计算 $\textit{ans}[i]$。
考虑正整数 $x$ 和 $x + 1$ 的二进制表示的如下两种情况。
当 $x$ 是偶数时，$x$ 的二进制表示的最低位是 $0$，$x + 1$ 的二进制表示等于 $x$ 的二进制表示的最低位从 $0$ 变成 $1$。
当 $x$ 是奇数时，$x$ 的二进制表示最低位有 $k$ 个 $1$ 且从低到高第 $k$ 位等于 $0$（位数从 $0$ 开始计数），其中 $k \ge 1$，$x + 1$ 的二进制表示等于 $x$ 的二进制表示的最低 $k$ 位从 $1$ 变成 $0$ 且从低到高第 $k$ 位从 $0$ 变成 $1$。
因此，$x ~|~ (x + 1)$ 的二进制表示的结果等于 $x$ 的二进制表示的最右边的 $0$ 变成 $1$。
为了使 $\textit{ans}[i]$ 的值最小，需要找到 $\textit{nums}[i]$ 的二进制表示中的可以变成 $0$ 的最左边的 $1$，满足将 $0$ 变成 $1$ 之后在其右侧没有任何 $0$。计算方法如下。
计算 $\textit{nums}[i]$ 的二进制表示的最低连续 $1$ 的最大位数 $k$，满足二进制表示最低位有 $k$ 个 $1$ 且从低到高第 $k$ 位等于 $0$（位数从 $0$ 开始计数）。
计算 $\textit{ans}[i] = \textit{nums}[i] - 2^{k - 1}$。
根据位运算的性质，计算方法如下：计算 $\textit{lowbit} = ((\textit{nums}[i] + 1) ~&~ (-\textit{nums}[i] - 1)) >> 1$，则 $\textit{lowbit}$ 等于上述 $2^{k - 1}$，$\textit{ans}[i] = \textit{nums}[i] - \textit{lowbit}$。
###Java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int n = nums.size();
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = find(nums.get(i));
}
return ans;
}
public int find(int num) {
if (num % 2 == 0) {
return -1;
} else {
int lowbit = ((num + 1) & (-num - 1)) >> 1;
return num - lowbit;
}
}
}
###C#
public class Solution {
public int[] MinBitwiseArray(IList<int> nums) {
int n = nums.Count;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = Find(nums[i]);
}
return ans;
}
public int Find(int num) {
if (num % 2 == 0) {
return -1;
} else {
int lowbit = ((num + 1) & (-num - 1)) >> 1;
return num - lowbit;
}
}
}
时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。答案数组中的每个元素的计算时间都是 $O(1)$。
空间复杂度：$O(1)$。注意返回值不计入空间复杂度。
