给你一个数组 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)$。
本题和 3510. 移除最小数对使数组有序 II 是一样的，请看 我的题解。
对于一个整数 $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)$。注意返回值不计入空间复杂度。
本题和 3315. 构造最小位运算数组 II 是一样的，请看 我的题解。
考虑 x or (x + 1) 是一个怎样的数。可以发现，x + 1 的二进制表示和 x 相比，其实就是把 x 从最低位开始的连续 $1$ 都变成 $0$，然后把下一位变成 $1$，更高位都不变。
因此我们找出 nums[i] 从最低位开始的连续 $1$，把连续 $1$ 的最后一位变成 $0$，就是答案。复杂度 $\mathcal{O}(n\log X)$，其中 $X = 10^9$ 是取值范围。
###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 {
// 求从最低位开始的连续 1
int p;
for (p = 0; x >> p & 1; p++);
// 把连续 1 的最后一位变成 0
ans.push_back(x ^ (1 << (p - 1)));
}
}
return ans;
}
};
给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。
请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。
示例 1：
输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 输出：2 解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。
示例 2：
输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 输出：0
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 3000 <= mat[i][j] <= 1040 <= threshold <= 105
前置知识：【图解】一张图秒懂二维前缀和。
预处理二维前缀和后，暴力的做法是写一个三重循环：
这样做的时间复杂度是 $\mathcal{O}(mn\min(m,n))$。
只需改一个地方，就能让算法的时间复杂度变小：
比如现在 $\textit{ans}=3$，那么枚举正方形的边长为 $1,2,3$ 是毫无意义的，不会让答案变得更大。所以直接从 $\textit{ans}+1=4$ 开始枚举更好。
###py
class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
m, n = len(mat), len(mat[0])
s = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(mat):
for j, x in enumerate(row):
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + x
# 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
def query(r1: int, c1: int, r2: int, c2: int) -> int:
return s[r2 + 1][c2 + 1] - s[r2 + 1][c1] - s[r1][c2 + 1] + s[r1][c1]
ans = 0
for i in range(m):
for j in range(n):
# 边长为 ans+1 的正方形，左上角在 (i, j)，右下角在 (i+ans, j+ans)
while i + ans < m and j + ans < n and query(i, j, i + ans, j + ans) <= threshold:
ans += 1
return ans
###java
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length;
int n = mat[0].length;
int[][] sum = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 边长为 ans+1 的正方形，左上角在 (i, j)，右下角在 (i+ans, j+ans)
while (i + ans < m && j + ans < n && query(sum, i, j, i + ans, j + ans) <= threshold) {
ans++;
}
}
}
return ans;
}
// 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
private int query(int[][] sum, int r1, int c1, int r2, int c2) {
return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];
}
}
###cpp
class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size();
vector sum(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];
}
}
// 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
auto query = [&](int r1, int c1, int r2, int c2) -> int {
return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];
};
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 边长为 ans+1 的正方形，左上角在 (i, j)，右下角在 (i+ans, j+ans)
while (i + ans < m && j + ans < n && query(i, j, i + ans, j + ans) <= threshold) {
ans++;
}
}
}
return ans;
}
};
###go
func maxSideLength(mat [][]int, threshold int) (ans int) {
m, n := len(mat), len(mat[0])
sum := make([][]int, m+1)
sum[0] = make([]int, n+1)
for i, row := range mat {
sum[i+1] = make([]int, n+1)
for j, x := range row {
sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + x
}
}
// 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
query := func(r1, c1, r2, c2 int) int {
return sum[r2+1][c2+1] - sum[r2+1][c1] - sum[r1][c2+1] + sum[r1][c1]
}
for i := range m {
for j := range n {
// 边长为 ans+1 的正方形，左上角在 (i, j)，右下角在 (i+ans, j+ans)
for i+ans < m && j+ans < n && query(i, j, i+ans, j+ans) <= threshold {
ans++
}
}
}
return
}
注：外层循环可以改成 i + ans < m 以及 j + ans < n。但测试了一下，并没有明显提升。
ans++ 最多执行 $\min(m,n)$ 次，三重循环的时间复杂度为 $\mathcal{O}(mn + \min(m,n)) = \mathcal{O}(mn)$。本题还有一种做法：枚举对角线，在对角线上做 不定长滑动窗口，把正方形的左上角和右下角看作滑动窗口的左右端点。这也可以做到 $\mathcal{O}(mn)$ 时间。
用这个思路解决如下问题：
欢迎在评论区分享你的代码。
见下面数据结构题单的「§1.6 二维前缀和」。
欢迎关注 B站@灵茶山艾府
本题需要用到一些二维前缀和（Prefix Sum）的知识，它是一维前缀和的延伸：
设二维数组 A 的大小为 m * n，行下标的范围为 [1, m]，列下标的范围为 [1, n]。
数组 P 是 A 的前缀和数组，等价于 P 中的每个元素 P[i][j]：
如果 i 和 j 均大于 0，那么 P[i][j] 表示 A 中以 (1, 1) 为左上角，(i, j) 为右下角的矩形区域的元素之和；
如果 i 和 j 中至少有一个等于 0，那么 P[i][j] 也等于 0。
数组 P 可以帮助我们在 $O(1)$ 的时间内求出任意一个矩形区域的元素之和。具体地，设我们需要求和的矩形区域的左上角为 (x1, y1)，右下角为 (x2, y2)，则该矩形区域的元素之和可以表示为：
sum = A[x1..x2][y1..y2]
= P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]
其正确性可以通过容斥原理得出。以下图为例，当 A 的大小为 8 * 5，需要求和的矩形区域（深绿色部分）的左上角为 (3, 2)，右下角为 (5, 5) 时，该矩形区域的元素之和为 P[5][5] - P[2][5] - P[5][1] + P[2][1]。
{:width=600}
那么如何得到数组 P 呢？我们按照行优先的顺序依次计算数组 P 中的每个元素，即当我们在计算 P[i][j] 时，数组 P 的前 i - 1 行，以及第 i 行的前 j - 1 个元素都已经计算完成。此时我们可以考虑 (i, j) 这个 1 * 1 的矩形区域，根据上面的等式，有：
A[i][j] = P[i][j] - P[i - 1][j] - P[i][j - 1] + P[i - 1][j - 1]
由于等式中的 A[i][j]，P[i - 1][j]，P[i][j - 1] 和 P[i - 1][j - 1] 均已知，我们可以通过：
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + A[i][j]
在 $O(1)$ 的时间计算出 P[i][j]。因此按照行优先的顺序，我们可以在 $O(MN)$ 的时间得到数组 P。在此之后，我们就可以很方便地在 $O(1)$ 的时间内求出任意一个矩形区域的元素之和了。
注意事项：
在大部分语言中，数组下标是从 0 而不是 1 开始，在实际的代码编写过程中需要考虑这一情况。
我们首先计算出数组 mat 的前缀和数组 P，随后依次枚举 mat 中的正方形，计算出每个正方形的元素之和。具体地，当数组 mat 的大小为 m * n 时，正方形的左上角可以是 mat 中的任意位置，边长不会超过 m 和 n 中的较小值 min(m, n)，这样我们就可以使用三重循环枚举所有的正方形，时间复杂度为 $O(MN * \min(M, N))$。由于我们可以借助数组 P 在 $O(1)$ 的时间计算任意正方形的元素之和，因此该算法的总时间复杂度为 $O(MN * \min(M, N))$。
若使用 C++ 语言编写上述算法，则可以恰好在规定时间内通过所有测试数据，但对于 Python 语言则无法通过。因此我们必须对该算法进行优化。
由于数组 mat 中的所有元素均为非负整数，因此若存在一个边长为 c 且元素之和不超过阈值的正方形，那一定存在一个边长为 1, 2, ..., c - 1 且元素之和不超过阈值的正方形（在边长为 c 的正方形内任取一个边长为 1, 2, ..., c - 1 的正方形即可）。这样我们可以使用二分查找的方法，找出最大的边长 c。二分查找的上界为 min(m, n)，下界为 1，在二分查找的过程中，若当前查找的边长为 c'，我们只需要枚举 mat 中所有边长为 c' 的正方形，并判断其中是否存在一个元素之和不超过阈值的正方形即可。
###C++
class Solution {
public:
int getRect(const vector<vector<int>>& P, int x1, int y1, int x2, int y2) {
return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1];
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> P(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int l = 1, r = min(m, n), ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
bool find = false;
for (int i = 1; i <= m - mid + 1; ++i) {
for (int j = 1; j <= n - mid + 1; ++j) {
if (getRect(P, i, j, i + mid - 1, j + mid - 1) <= threshold) {
find = true;
}
}
}
if (find) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
return ans;
}
};
###Python
class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
m, n = len(mat), len(mat[0])
P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]
def getRect(x1, y1, x2, y2):
return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]
l, r, ans = 1, min(m, n), 0
while l <= r:
mid = (l + r) // 2
find = any(getRect(i, j, i + mid - 1, j + mid - 1) <= threshold for i in range(1, m - mid + 2) for j in range(1, n - mid + 2))
if find:
ans = mid
l = mid + 1
else:
r = mid - 1
return ans
###Java
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length, n = mat[0].length;
int[][] P = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int l = 1, r = Math.min(m, n), ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
boolean find = false;
for (int i = 1; i <= m - mid + 1; i++) {
for (int j = 1; j <= n - mid + 1; j++) {
int sum = P[i + mid - 1][j + mid - 1] - P[i - 1][j + mid - 1] - P[i + mid - 1][j - 1] + P[i - 1][j - 1];
if (sum <= threshold) {
find = true;
break;
}
}
if (find) break;
}
if (find) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
###C#
public class Solution {
public int MaxSideLength(int[][] mat, int threshold) {
int m = mat.Length, n = mat[0].Length;
int[,] P = new int[m + 1, n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
P[i, j] = P[i - 1, j] + P[i, j - 1] - P[i - 1, j - 1] + mat[i - 1][j - 1];
}
}
int l = 1, r = Math.Min(m, n), ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
bool find = false;
for (int i = 1; i <= m - mid + 1; i++) {
for (int j = 1; j <= n - mid + 1; j++) {
int sum = P[i + mid - 1, j + mid - 1] - P[i - 1, j + mid - 1] - P[i + mid - 1, j - 1] + P[i - 1, j - 1];
if (sum <= threshold) {
find = true;
break;
}
}
if (find) break;
}
if (find) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
###Go
func maxSideLength(mat [][]int, threshold int) int {
m, n := len(mat), len(mat[0])
P := make([][]int, m+1)
for i := range P {
P[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1]
}
}
l, r, ans := 1, min(m, n), 0
for l <= r {
mid := (l + r) / 2
find := false
for i := 1; i <= m-mid+1; i++ {
for j := 1; j <= n-mid+1; j++ {
sum := P[i+mid-1][j+mid-1] - P[i-1][j+mid-1] - P[i+mid-1][j-1] + P[i-1][j-1]
if sum <= threshold {
find = true
break
}
}
if find {
break
}
}
if find {
ans = mid
l = mid + 1
} else {
r = mid - 1
}
}
return ans
}
###C
int maxSideLength(int** mat, int matSize, int* matColSize, int threshold) {
int m = matSize, n = matColSize[0];
int** P = (int**)malloc((m + 1) * sizeof(int*));
for (int i = 0; i <= m; i++) {
P[i] = (int*)calloc(n + 1, sizeof(int));
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1];
}
}
int l = 1, r = (m < n ? m : n), ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
int find = 0;
for (int i = 1; i <= m - mid + 1; i++) {
for (int j = 1; j <= n - mid + 1; j++) {
int sum = P[i+mid-1][j+mid-1] - P[i-1][j+mid-1] - P[i+mid-1][j-1] + P[i-1][j-1];
if (sum <= threshold) {
find = 1;
break;
}
}
if (find) break;
}
if (find) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
for (int i = 0; i <= m; i++) {
free(P[i]);
}
free(P);
return ans;
}
###JavaScript
var maxSideLength = function(mat, threshold) {
const m = mat.length, n = mat[0].length;
const P = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1];
}
}
let l = 1, r = Math.min(m, n), ans = 0;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
let find = false;
for (let i = 1; i <= m - mid + 1; i++) {
for (let j = 1; j <= n - mid + 1; j++) {
const sum = P[i + mid - 1][j + mid - 1] - P[i - 1][j + mid - 1] -
P[i + mid - 1][j - 1] + P[i - 1][j - 1];
if (sum <= threshold) {
find = true;
break;
}
}
if (find) break;
}
if (find) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
};
###TypeScript
function maxSideLength(mat: number[][], threshold: number): number {
const m = mat.length, n = mat[0].length;
const P: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1];
}
}
let l = 1, r = Math.min(m, n), ans = 0;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
let find = false;
for (let i = 1; i <= m - mid + 1; i++) {
for (let j = 1; j <= n - mid + 1; j++) {
const sum = P[i + mid - 1][j + mid - 1] - P[i - 1][j + mid - 1] -
P[i + mid - 1][j - 1] + P[i - 1][j - 1];
if (sum <= threshold) {
find = true;
break;
}
}
if (find) break;
}
if (find) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
###Rust
impl Solution {
pub fn max_side_length(mat: Vec<Vec<i32>>, threshold: i32) -> i32 {
let m = mat.len();
let n = mat[0].len();
let mut P = vec![vec![0; n + 1]; m + 1];
for i in 1..=m {
for j in 1..=n {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1] as i32;
}
}
let mut l = 1;
let mut r = m.min(n);
let mut ans = 0;
while l <= r {
let mid = (l + r) / 2;
let mut find = false;
for i in 1..=(m - mid + 1) {
for j in 1..=(n - mid + 1) {
let sum = P[i + mid - 1][j + mid - 1] - P[i - 1][j + mid - 1] -
P[i + mid - 1][j - 1] + P[i - 1][j - 1];
if sum <= threshold {
find = true;
break;
}
}
if find {
break;
}
}
if find {
ans = mid as i32;
l = mid + 1;
} else {
r = mid - 1;
}
}
ans
}
}
复杂度分析
时间复杂度：$O(MN * \log\min(M, N))$。二分查找的次数为 $O(\log\min(M, N))$，在每次二分查找中，需要枚举所有边长为 c' 的矩形，数量为 $O(MN)$，因此总时间复杂度为 $O(MN * \log\min(M, N))$。
空间复杂度：$O(MN)$。
在方法一中，我们使用二分查找的方法，将时间复杂度为 $O(MN * \min(M, N))$ 的枚举算法优化至 $O(MN * \log \min(M, N))$。那么我们还可以继续优化下去吗？
我们舍弃二分查找的思路，转而想一想如何直接对枚举算法进行优化。枚举算法中包括三重循环，其中前两重循环枚举正方形的左上角位置，似乎没有什么优化的空间；而第三重循环枚举的是正方形的边长，对此我们很容易想到两个优化的思路：
如果边长为 c 的正方形的元素之和已经超过阈值，那么我们就没有必要枚举更大的边长了。这是因为数组 mat 中的所有元素均为非负整数，如果固定了左上角的位置 (i, j)（即前两重循环），那么随着边长的增大，正方形的元素之和也会增大。
由于我们的目标是找到边长最大的正方形，那么如果我们在前两重循环枚举到 (i, j) 之前已经找到了一个边长为 c' 的正方形，那么在枚举以 (i, j) 为左上角的正方形时，我们可以忽略所有边长小于等于 c' 的正方形，直接从 c' + 1 开始枚举。
基于上述的两个优化，我们可以编写出如下的代码：
###C++
class Solution {
public:
int getRect(const vector<vector<int>>& P, int x1, int y1, int x2, int y2) {
return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1];
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> P(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int r = min(m, n), ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int c = ans + 1; c <= r; ++c) {
if (i + c - 1 <= m && j + c - 1 <= n && getRect(P, i, j, i + c - 1, j + c - 1) <= threshold) {
++ans;
}
else {
break;
}
}
}
}
return ans;
}
};
###Python
class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
m, n = len(mat), len(mat[0])
P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]
def getRect(x1, y1, x2, y2):
return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]
r, ans = min(m, n), 0
for i in range(1, m + 1):
for j in range(1, n + 1):
for c in range(ans + 1, r + 1):
if i + c - 1 <= m and j + c - 1 <= n and getRect(i, j, i + c - 1, j + c - 1) <= threshold:
ans += 1
else:
break
return ans
###Java
class Solution {
private int getRect(int[][] P, int x1, int y1, int x2, int y2) {
return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1];
}
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length, n = mat[0].length;
int[][] P = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int r = Math.min(m, n), ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int c = ans + 1; c <= r; ++c) {
if (i + c - 1 <= m && j + c - 1 <= n && getRect(P, i, j, i + c - 1, j + c - 1) <= threshold) {
++ans;
} else {
break;
}
}
}
}
return ans;
}
}
###C#
public class Solution {
private int GetRect(int[,] P, int x1, int y1, int x2, int y2) {
return P[x2, y2] - P[x1 - 1, y2] - P[x2, y1 - 1] + P[x1 - 1, y1 - 1];
}
public int MaxSideLength(int[][] mat, int threshold) {
int m = mat.Length, n = mat[0].Length;
int[,] P = new int[m + 1, n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
P[i, j] = P[i - 1, j] + P[i, j - 1] - P[i - 1, j - 1] + mat[i - 1][j - 1];
}
}
int r = Math.Min(m, n), ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int c = ans + 1; c <= r; ++c) {
if (i + c - 1 <= m && j + c - 1 <= n && GetRect(P, i, j, i + c - 1, j + c - 1) <= threshold) {
++ans;
} else {
break;
}
}
}
}
return ans;
}
}
###Go
func maxSideLength(mat [][]int, threshold int) int {
m, n := len(mat), len(mat[0])
P := make([][]int, m+1)
for i := range P {
P[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1]
}
}
getRect := func(x1, y1, x2, y2 int) int {
return P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]
}
r := min(m, n)
ans := 0
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
for c := ans + 1; c <= r; c++ {
if i+c-1 <= m && j+c-1 <= n && getRect(i, j, i+c-1, j+c-1) <= threshold {
ans = c
} else {
break
}
}
}
}
return ans
}
###C
int getRect(int** P, int x1, int y1, int x2, int y2) {
return P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1];
}
int maxSideLength(int** mat, int matSize, int* matColSize, int threshold) {
int m = matSize, n = matColSize[0];
int** P = (int**)malloc((m + 1) * sizeof(int*));
for (int i = 0; i <= m; i++) {
P[i] = (int*)calloc(n + 1, sizeof(int));
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1];
}
}
int r = (m < n ? m : n);
int ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int c = ans + 1; c <= r; c++) {
if (i + c - 1 <= m && j + c - 1 <= n && getRect(P, i, j, i + c - 1, j + c - 1) <= threshold) {
ans = c;
} else {
break;
}
}
}
}
for (int i = 0; i <= m; i++) {
free(P[i]);
}
free(P);
return ans;
}
###JavaScript
var maxSideLength = function(mat, threshold) {
const m = mat.length, n = mat[0].length;
const P = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1];
}
}
const getRect = (x1, y1, x2, y2) => {
return P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1];
};
const r = Math.min(m, n);
let ans = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
for (let c = ans + 1; c <= r; c++) {
if (i + c - 1 <= m && j + c - 1 <= n && getRect(i, j, i + c - 1, j + c - 1) <= threshold) {
ans = c;
} else {
break;
}
}
}
}
return ans;
};
###TypeScript
function maxSideLength(mat: number[][], threshold: number): number {
const m = mat.length, n = mat[0].length;
const P: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1];
}
}
const getRect = (x1: number, y1: number, x2: number, y2: number): number => {
return P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1];
};
const r = Math.min(m, n);
let ans = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
for (let c = ans + 1; c <= r; c++) {
if (i + c - 1 <= m && j + c - 1 <= n && getRect(i, j, i + c - 1, j + c - 1) <= threshold) {
ans = c;
} else {
break;
}
}
}
}
return ans;
}
###Rust
impl Solution {
fn get_rect(P: &Vec<Vec<i32>>, x1: usize, y1: usize, x2: usize, y2: usize) -> i32 {
P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]
}
pub fn max_side_length(mat: Vec<Vec<i32>>, threshold: i32) -> i32 {
let m = mat.len();
let n = mat[0].len();
let mut P = vec![vec![0; n + 1]; m + 1];
for i in 1..=m {
for j in 1..=n {
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1];
}
}
let r = m.min(n);
let mut ans = 0;
for i in 1..=m {
for j in 1..=n {
for c in (ans + 1)..=r {
if i + c - 1 <= m && j + c - 1 <= n &&
Self::get_rect(&P, i, j, i + c - 1, j + c - 1) <= threshold {
ans = c;
} else {
break;
}
}
}
}
ans as i32
}
}
优化后的算法时间复杂度是多少呢？显然，它等于第三重循环中边长 c 被枚举的次数。由于优化后第三重循环的上下界并不固定，因此我们需要使用一些技巧，将第三重循环中边长 c 的枚举分为两类：
成功枚举：如果当前枚举的边长为 c 的正方形的元素之和不超过阈值，那么称此为一次「成功枚举」。在进行成功枚举后，我们找到了比之前边长更大的正方形。
失败枚举：如果当前枚举的边长为 c 的正方形的元素之和大于阈值，那么称此为一次「失败枚举」。在进行失败枚举后，我们就没有必要枚举更大的边长了，会直接跳出第三重循环。
对于「成功枚举」而言，由于每进行一次「成功枚举」，我们都会得到一个边长更大的正方形，而边长的最大值不会超过 min(m, n)，因此「成功枚举」的总次数也不会超过 min(m, n)；对于「失败枚举」而言，由于每进行一次「失败枚举」，都会直接跳出第三重循环，因此每一个左上角的位置 (i, j) 最多只会对应一次「失败枚举」，即「失败枚举」的总次数不会超过 mn。因此，优化后算法的时间复杂度为 $O(\min(M, N) + MN) = O(MN)$，它比二分查找更优。
复杂度分析
时间复杂度：$O(MN)$。这看上去很不可思议，但它确实比方法一中二分查找的时间复杂度更低。
空间复杂度：$O(MN)$。
遍历所有可能的正方形区域，具体的算法流程是：1.考虑正方形的边长从 1 到 $Min(M,N)$（M 为矩阵长度，N 为矩阵宽度）2.考虑正方形右下角的坐标从 (0, 0) 到 (M, N) 3.判断正方形是否存在（可能会超出边界，通过左上角坐标判断），如果存在则验证该正方形区域的元素总和。
下面引入二维前缀和的计算方法，通过预处理可以在 $O(1)$ 时间内计算出一块区域内元素的总和。
首先是预处理，在 $O(N^2)$ 时间内计算出二维前缀和 dp[i][j]：从 (0, 0) 到 (i, j) 内元素的总和。
已知 dp[i][j] 必定包含一个元素 mat[i][j]，假设我们已经计算出部分前缀和 dp[x][y]（x < i 且 y < j），那么 dp[i][j] = mat[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]。
下面通过一组动画来理解这个过程（图片较大，请点击左下角播放）：
我们需要计算黑色虚线区域即 dp[i][j]，先加上右下角元素mat[i][j]，接着加上mat[i][j]上方区域的前缀和dp[i - 1][j]以及左边区域的前缀和dp[i][j - 1]，但左上角一块区域被加了两次，因此还要再扣去这块区域dp[i - 1][j - 1]。
<,,,>
预处理完二维前缀和，我们可以逆向这个过程，计算出某一块特定区域内元素总和。例如计算下面的红色区域，其右下角坐标为 (i, j)，长度和宽度为 k，则可以将绿色区域 dp[i][j] 减去红色区域相邻的上方区域dp[i - k][j]以及相邻的左边区域dp[i][j - k]，最后补上被多减一次的左上方区域dp[i - k][j - k]。
图示（图片较大，请点击左下角播放）：
<,,,,>
###java
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length, n = mat[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
}
int ans = 0;
for (int k = 1; k <= Math.min(m, n); k++) {
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (i - k < 0 || j - k < 0) {
continue;
}
int tmp = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k];
if (tmp <= threshold) {
ans = Math.max(ans, k);
}
}
}
}
return ans;
}
}
查找的正方形的边长越长，其计算出来的元素总和越大。
我们可以二分正方形的边长，在满足阈值条件下尽可能地扩大正方形的边长，其等价于在升序数组中查找一个小于等于 k 的最大元素。
二分的具体思路：
###java
class Solution {
int m, n;
int[][] dp;
public int maxSideLength(int[][] mat, int threshold) {
m = mat.length;
n = mat[0].length;
dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
}
int l = 0, h = Math.min(m, n);
while (l <= h) {
int mid = l + (h - l) / 2;
if (l == h || l + 1 == h) {
break;
}
if (help(mid, threshold)) {
l = mid;
} else {
h = mid - 1;
}
}
if (help(h, threshold)) {
return h;
} else {
return l;
}
}
public boolean help(int k, int threshold) {
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (i - k < 0 || j - k < 0) {
continue;
}
if (dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k] <= threshold) {
return true;
}
}
}
return false;
}
}
如果该题解对你有帮助，点个赞再走呗~
