欢迎大家加QQ群：623375442，可以方便群里面交流。
这周双周赛本质就两题，区别只在于取数范围。范围较大的那个能过，另一题简单版本就一定可以过。我就放2个题解了。
100384. Find the Power of K-Size Subarrays II
给你一个长度为 n 的整数数组 nums 和一个正整数 k 。
一个数组的 能量值 定义为：
- 如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
- 否则为 -1 。
你需要求出 nums 中所有长度为 k 的 子数组 的能量值。
请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。
测试样例：
输入：nums = [1,2,3,4,3,2,5], k = 3
输出：[3,4,-1,-1,-1]
解释：nums 中总共有 5 个长度为 3 的子数组：
- [1, 2, 3] 中最大元素为 3 。
- [2, 3, 4] 中最大元素为 4 。
- [3, 4, 3] 中元素 不是 连续的。
- [4, 3, 2] 中元素 不是 上升的。
- [3, 2, 5] 中元素 不是 连续的。
解答：利用一个count记录一下连续的数组数量，数组数量大于k个，那么当前位置就是当前数字。否则-1。
class Solution {
public int[] resultsArray(int[] nums, int k) {
// k = 1需要注意一下，后面的逻辑从1开始，会WA
if (nums.length == 1 || k == 1) {
return nums;
}
int[] res = new int[nums.length - k + 1];
// count记录连续上升元素数量
int count = 1;
for (int i = 1; i < nums.length; ++i) {
if (nums[i] == nums[i - 1] + 1) {
++count;
} else {
count = 1;
}
if (i >= k - 1) {
res[i - k + 1] = count >= k ? nums[i] : -1;
}
}
return res;
}
}100401. Maximum Value Sum by Placing Three Rooks II
给你一个 m x n 的二维整数数组 board ，它表示一个国际象棋棋盘，其中 board[i][j] 表示格子 (i, j) 的 价值 。
处于 同一行 或者 同一列 车会互相 攻击 。你需要在棋盘上放三个车，确保它们两两之间都 无法互相攻击 。
请你返回满足上述条件下，三个车所在格子 值 之和 最大 为多少。
测试样例：
输入：board = [[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]
输出：4
解释：
我们可以将车分别放在格子 (0, 2) ，(1, 3) 和 (2, 1) 处，价值之和为 1 + 1 + 2 = 4 。
解答：这题思路有点难想到，实现也有点麻烦。思路大概就是我们假设选择的行为A < B < C。那么我们利用B这个中间位置。这样A和C的取数位置分别是A in [0, B - 1]和C in [B + 1, m - 1]。这样我们分别计算A，B，C这三个区间的3个最大列结果。然后暴力枚举27种情况，看固定B位置时，最大的结果。
class Solution {
public long maximumValueSum(int[][] board) {
int m = board.length, n = board[0].length;
// 计算A这个区域的最大3个列
int[][][] downBest = new int[m][][];
{
int[] row = new int[n];
Arrays.fill(row, Integer.MIN_VALUE);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
row[j] = Math.max(row[j], board[i][j]);
}
downBest[i] = findBestThree(row);
}
}
// 计算C这个区域的最大3个列
int[][][] upBest = new int[m][][];
{
int[] row = new int[n];
Arrays.fill(row, Integer.MIN_VALUE);
for (int i = m - 1; i >= 0; --i) {
for (int j = 0; j < n; ++j) {
row[j] = Math.max(row[j], board[i][j]);
}
upBest[i] = findBestThree(row);
}
}
long best = Long.MIN_VALUE;
// 便利B
for (int i = 1; i < m - 1; ++i) {
int[] row = new int[n];
Arrays.fill(row, Integer.MIN_VALUE);
for (int j = 0; j < n; ++j) {
row[j] = Math.max(row[j], board[i][j]);
}
int[][] rowBest = findBestThree(row);
// 暴力枚举27种情况，查询最大数值
best = Math.max(best, countBest(downBest[i - 1], rowBest, upBest[i + 1]));
}
return best;
}
private int[][] findBestThree(int[] row) {
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (Integer.compare(row[a], row[b])));
for (int i = 0; i < row.length; ++i) {
queue.add(i);
if (queue.size() > 3) {
queue.poll();
}
}
int[][] res = new int[3][2];
for (int i = 0; i < 3; ++i) {
int tmp = queue.poll();
res[3 - i - 1][0] = tmp;
res[3 - i - 1][1] = row[tmp];
}
return res;
}
private long countBest(int[][] a, int[][] b, int[][] c) {
long res = Long.MIN_VALUE;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (a[i][0] != b[j][0] && a[i][0] != c[k][0] && b[j][0] != c[k][0]) {
res = Math.max(0L + a[i][1] + b[j][1] + c[k][1], res);
}
}
}
}
return res;
}
}