🌟欢迎来到 我的博客 —— 探索技术的无限可能！
8.寻找数组的中心下标
题目链接：724. 寻找数组的中心下标
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。
示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示：
1 <= nums.length <= 104
-1000 <= nums[i] <= 1000
题解：
方法：遍历数组
class Solution { public int pivotIndex(int[] nums) { int s = 0; for (int num : nums) { s += num; } int leftS = 0; for (int i = 0; i < nums.length; i++) { if (leftS * 2 == s - nums[i]) { return i; } leftS += nums[i]; } return -1; } }
9.最小化曼哈顿距离
题目链接：3102. 最小化曼哈顿距离
给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。
两点之间的距离定义为它们的
曼哈顿距离
。
请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。
示例 1：
输入：points = [[3,10],[5,15],[10,2],[4,4]]
输出：12
解释：移除每个点后的最大距离如下所示：
- 移除第 0 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间，为 |5 - 10| + |15 - 2| = 18 。
- 移除第 1 个点后，最大距离在点 (3, 10) 和 (10, 2) 之间，为 |3 - 10| + |10 - 2| = 15 。
- 移除第 2 个点后，最大距离在点 (5, 15) 和 (4, 4) 之间，为 |5 - 4| + |15 - 4| = 12 。
- 移除第 3 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间的，为 |5 - 10| + |15 - 2| = 18 。
在恰好移除一个点后，任意两点之间的最大距离可能的最小值是 12 。
示例 2：
输入：points = [[1,1],[1,1],[1,1]]
输出：0
解释：移除任一点后，任意两点之间的最大距离都是 0 。
提示：
3 <= points.length <= 105
points[i].length == 2
1 <= points[i][0], points[i][1] <= 108
题解：
方法：维护最大次大、最小次小
class Solution { public int minimumDistance(int[][] points) { final int INF = Integer.MAX_VALUE; int maxX1 = -INF, maxX2 = -INF, maxY1 = -INF, maxY2 = -INF; int minX1 = INF, minX2 = INF, minY1 = INF, minY2 = INF; for (int[] p : points) { int x = p[0] + p[1]; int y = p[1] - p[0]; // x 最大次大 if (x > maxX1) { maxX2 = maxX1; maxX1 = x; } else if (x > maxX2) { maxX2 = x; } // x 最小次小 if (x < minX1) { minX2 = minX1; minX1 = x; } else if (x < minX2) { minX2 = x; } // y 最大次大 if (y > maxY1) { maxY2 = maxY1; maxY1 = y; } else if (y > maxY2) { maxY2 = y; } // y 最小次小 if (y < minY1) { minY2 = minY1; minY1 = y; } else if (y < minY2) { minY2 = y; } } int ans = INF; for (int[] p : points) { int x = p[0] + p[1]; int y = p[1] - p[0]; int dx = (x == maxX1 ? maxX2 : maxX1) - (x == minX1 ? minX2 : minX1); int dy = (y == maxY1 ? maxY2 : maxY1) - (y == minY1 ? minY2 : minY1); ans = Math.min(ans, Math.max(dx, dy)); } return ans; } }
10.统计移除递增子数组的数目 I
题目链接：2970. 统计移除递增子数组的数目 I
给你一个下标从 0 开始的 正 整数数组 nums 。
如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。
请你返回 nums 中 移除递增 子数组的总数目。
注意 ，剩余元素为空的数组也视为是递增的。
子数组 指的是一个数组中一段非空且连续的元素序列。
示例 1：
输入：nums = [1,2,3,4]
输出：10
解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3],
[2,3,4] 和 [1,2,3,4]。移
除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。
示例 2：
输入：nums = [6,5,7,8]
输出：7
解释：7 个移除递增子数组分别为：[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8]
。
nums 中只有这 7 个移除递增子数组。
示例 3：
输入：nums = [8,7,6,6]
输出：3
解释：3 个移除递增子数组分别为：[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为
移除 [8,7] 后 nums 变为 [6,6] ，它不是严格递增的。
提示：
1 <= nums.length <= 50
1 <= nums[i] <= 50
题解：
方法：双指针
class Solution { public int incremovableSubarrayCount(int[] nums) { int i = 0, n = nums.length; while (i + 1 < n && nums[i] < nums[i + 1]) { ++i; } if (i == n - 1) { return n * (n + 1) / 2; } int ans = i + 2; for (int j = n - 1; j > 0; --j) { while (i >= 0 && nums[i] >= nums[j]) { --i; } ans += i + 2; if (nums[j - 1] >= nums[j]) { break; } } return ans; } }
11.统计移除递增子数组的数目 II
给你一个下标从 0 开始的 正 整数数组 nums 。
如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。
请你返回 nums 中 移除递增 子数组的总数目。
注意 ，剩余元素为空的数组也视为是递增的。
子数组 指的是一个数组中一段连续的元素序列。
示例 1：
输入：nums = [1,2,3,4]
输出：10
解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3],
[2,3,4] 和 [1,2,3,4]。移 除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。
示例 2：
输入：nums = [6,5,7,8]
输出：7
解释：7 个移除递增子数组分别为：[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8]
。
nums 中只有这 7 个移除递增子数组。
示例 3：
输入：nums = [8,7,6,6]
输出：3
解释：3 个移除递增子数组分别为：[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为移除 [8,7] 后 nums 变为 [6,6] ，它不是严格递增的。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109
题解：
方法：双指针
class Solution { public long incremovableSubarrayCount(int[] a) { int n = a.length; int i = 0; while (i < n - 1 && a[i] < a[i + 1]) { i++; } if (i == n - 1) { // 每个非空子数组都可以移除 return (long) n * (n + 1) / 2; } long ans = i + 2; // 不保留后缀的情况，一共 i+2 个 // 枚举保留的后缀为 a[j:] for (int j = n - 1; j == n - 1 || a[j] < a[j + 1]; j--) { while (i >= 0 && a[i] >= a[j]) { i--; } // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个 ans += i + 2; } return ans; } }
12.最小数字游戏
题目链接：2974. 最小数字游戏
你有一个下标从 0 开始、长度为 偶数 的整数数组 nums ，同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏，游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下：
每一轮，Alice 先从 nums 中移除一个 最小 元素，然后 Bob 执行同样的操作。
接着，Bob 会将移除的元素添加到数组 arr 中，然后 Alice 也执行同样的操作。
游戏持续进行，直到 nums 变为空。
返回结果数组 arr 。
示例 1：
输入：nums = [5,4,2,3]
输出：[3,2,5,4]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 3 。然后 Bob 先将 3 添加到 arr 中，接着 Alice 再将 2
添加到 arr 中。于是 arr = [3,2] 。
第二轮开始时，nums = [5,4] 。Alice 先移除 4 ，然后 Bob 移除 5 。接着他们都将元素添加到 arr 中，arr
变为 [3,2,5,4] 。
示例 2：
输入：nums = [2,5]
输出：[5,2]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 5 。然后 Bob 先将 5 添加到 arr 中，接着 Alice 再将 2
添加到 arr 中。于是 arr = [5,2] 。
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100
nums.length % 2 == 0
题解：
方法：模拟 + 优先队列
class Solution { public int[] numberGame(int[] nums) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int x : nums) { pq.offer(x); } int[] ans = new int[nums.length]; int i = 0; while (!pq.isEmpty()) { int a = pq.poll(); ans[i++] = pq.poll(); ans[i++] = a; } return ans; } }
13.判断一个数组是否可以变为有序
题目链接：3011. 判断一个数组是否可以变为有序
给你一个下标从 0 开始且全是 正 整数的数组 nums 。
一次 操作 中，如果两个 相邻 元素在二进制下数位为 1 的数目 相同 ，那么你可以将这两个元素交换。你可以执行这个操作 任意次 （也可以 0 次）。
如果你可以使数组变有序，请你返回 true ，否则返回 false 。
示例 1：
输入：nums = [8,4,2,30,15]
输出：true
解释：我们先观察每个元素的二进制表示。 2 ，4 和 8 分别都只有一个数位为 1 ，分别为 “10” ，“100” 和 “1000”
。15 和 30 分别有 4 个数位为 1 ：“1111” 和 “11110” 。
我们可以通过 4 个操作使数组有序：
- 交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。
- 交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。
- 交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。
- 交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 ，数组变为 [2,4,8,15,30] 。
数组变成有序的，所以我们返回 true 。
注意我们还可以通过其他的操作序列使数组变得有序。
示例 2：
输入：nums = [1,2,3,4,5]
输出：true
解释：数组已经是有序的，所以我们返回 true 。
示例 3：
输入：nums = [3,16,8,4,2]
输出：false
解释：无法通过操作使数组变为有序。
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 28
题解：
方法：排序
class Solution { public boolean canSortArray(int[] nums) { int n = nums.length; for (int i = 0; i < n;) { int start = i; int ones = Integer.bitCount(nums[i++]); while (i < n && Integer.bitCount(nums[i]) == ones) { i++; } Arrays.sort(nums, start, i); } for (int i = 1; i < n; i++) { if (nums[i] < nums[i - 1]) { return false; } } return true; } }
14.保持城市天际线
题目链接：807. 保持城市天际线
给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。
城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。
我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。 高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。
在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。
示例 1：
输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：35
解释：建筑物的高度如上图中心所示。
用红色绘制从不同方向观看得到的天际线。
在不影响天际线的情况下，增加建筑物的高度：
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7], [9, 4, 8, 7], [3, 3, 3, 3] ]
示例 2：
输入：grid = [[0,0,0],[0,0,0],[0,0,0]]
输出：0
解释：增加任何建筑物的高度都会导致天际线的变化。
提示：
n == grid.length
n == grid[r].length
2 <= n <= 50
0 <= grid[r][c] <= 100
题解：
方法：贪心
class Solution { public int maxIncreaseKeepingSkyline(int[][] grid) { int n = grid.length; int m = grid[0].length; int[] rowMax = new int[n]; int[] colMax = new int[m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { rowMax[i] = Math.max(rowMax[i], grid[i][j]); colMax[j] = Math.max(colMax[j], grid[i][j]); } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ans += Math.min(rowMax[i], colMax[j]) - grid[i][j]; } } return ans; } }
