欢迎大家加QQ群：623375442，可以方便群里面交流。最后一题Coding起来有点麻烦。第二题和第四题可以用同一个思路，我就直接跳过第二题的题解了。
100490. Transformed Array
给你一个整数数组 nums，它表示一个循环数组。请你遵循以下规则创建一个大小 相同 的新数组 result ：
对于每个下标 i（其中 0 <= i < nums.length），独立执行以下操作：
- 如果 nums[i] > 0：从下标 i 开始，向 右 移动 nums[i] 步，在循环数组中落脚的下标对应的值赋给 result[i]。
- 如果 nums[i] < 0：从下标 i 开始，向 左 移动 abs(nums[i]) 步，在循环数组中落脚的下标对应的值赋给 result[i]。
- 如果 nums[i] == 0：将 nums[i] 的值赋给 result[i]。
返回新数组 result。
注意：由于 nums 是循环数组，向右移动超过最后一个元素时将回到开头，向左移动超过第一个元素时将回到末尾。
测试样例：
输入：nums = [3,-2,1,1]
输出：[1,1,1,3]
解释：
- 对于 nums[0] 等于 3，向右移动 3 步到 nums[3]，因此 result[0] 为 1。
- 对于 nums[1] 等于 -2，向左移动 2 步到 nums[3]，因此 result[1] 为 1。
- 对于 nums[2] 等于 1，向右移动 1 步到 nums[3]，因此 result[2] 为 1。
- 对于 nums[3] 等于 1，向右移动 1 步到 nums[0]，因此 result[3] 为 3。
解答：按照题意，暴力计算。
class Solution {
public int[] constructTransformedArray(int[] nums) {
int len = nums.length;
int[] res = new int[len];
for (int i = 0; i < len; ++i) {
if (nums[i] >= 0) {
res[i] = nums[(i + nums[i]) % nums.length];
} else {
res[i] = nums[((i + nums[i]) % nums.length + nums.length) % nums.length];
}
}
return res;
}
}100492. Maximum Subarray Sum With Length Divisible by K
给你一个整数数组 nums 和一个整数 k 。
返回 nums 中一个 非空子数组 的 最大 和，要求该子数组的长度可以 被 k 整除 。
子数组 是数组中一个连续的、非空的元素序列。
测试样例：
输入：nums = [1,2], k = 1
输出：3
解释：子数组 [1, 2] 的和为 3，其长度为 2，可以被 1 整除。
解答：前缀和可以解决这题。注意，子数组长度是k，所以记录每k个位置的最小前缀和。
class Solution {
public long maxSubarraySum(int[] nums, int k) {
long[] max = new long[k];
Arrays.fill(max, Long.MAX_VALUE / 2);
max[0] = 0;
long sum = 0, res = Long.MIN_VALUE;
for (int i = 0; i < nums.length; ++i) {
sum += nums[i];
if (i >= k - 1) res = Math.max(res, sum - max[(i + 1) % k]);
max[(i + 1) % k] = Math.min(max[(i + 1) % k], sum);
}
return res;
}
}100514. Maximum Area Rectangle With Point Constraints II
在无限平面上有 n 个点。给定两个整数数组 xCoord 和 yCoord，其中 (xCoord[i], yCoord[i]) 表示第 i 个点的坐标。
你的任务是找出满足以下条件的矩形可能的 最大 面积：
- 矩形的四个顶点必须是数组中的 四个 点。
- 矩形的内部或边界上 不能 包含任何其他点。
- 矩形的边与坐标轴 平行 。
返回可以获得的 最大面积 ，如果无法形成这样的矩形，则返回 -1。
测试样例：
输入：xCoord = [1,1,3,3], yCoord = [1,3,1,3]
输出：4
解释：我们可以用这 4 个点作为顶点构成一个矩形，并且矩形内部或边界上没有其他点。因此，最大面积为 4 。
解答：这题思路还是挺简单的。首先我们按照x的大小排序，如果x相同，那按照y的大小排序。因为矩形的边界包含任何其他点，所以挑选的时候，必然是x相同，则y就是按循序的下一个点。
其次内部上不能有任何点，我们用一个线段树记录每个y的最小x情况，如果区间的x小于边界，那么必然就存在内部点。
class Solution {
public long maxRectangleArea(int[] xCoord, int[] yCoord) {
int len = xCoord.length;
HashMap<Integer, TreeMap<Integer, Integer>> yMap = new HashMap<>();
for (int i = 0; i < len; ++i) {
if (!yMap.containsKey(yCoord[i])) {
TreeMap<Integer, Integer> add = new TreeMap<>();
add.put(Integer.MAX_VALUE, 1);
yMap.put(yCoord[i], add);
}
TreeMap<Integer, Integer> tmp = yMap.get(yCoord[i]);
tmp.put(xCoord[i], tmp.getOrDefault(xCoord[i], 0) + 1);
}
Integer[] sort = new Integer[len];
for (int i = 0; i < len; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (xCoord[a] != xCoord[b] ? Integer.compare(xCoord[a], xCoord[b]) : Integer.compare(yCoord[a], yCoord[b])));
// 线段树，记录每个y对应的最小x，这样可以快速计算区间情况
SegmentTree tree = new SegmentTree(yMap);
long res = -1;
for (int i = 0; i < len - 1; ++i) {
int x = xCoord[sort[i]], yPos1 = yCoord[sort[i]];
// 下一个点的x必须相同，否则代表当前x已经用完
if (xCoord[sort[i]] == xCoord[sort[i + 1]]) {
int yPos2 = yCoord[sort[i + 1]];
int h1 = yMap.get(yPos1).higherKey(x), h2 = yMap.get(yPos2).higherKey(x);
// 两个yPos对应的下一个x位置必须存在且相同。不相同的话，无法满足与坐标轴平行的要求
// 区间内不存在额外点
if (h1 != Integer.MAX_VALUE && h1 == h2 && tree.minRange(yPos1, yPos2) > h1) {
long d1 = yPos2 - yPos1, d2 = h2 - x;
res = Math.max(res, d1 * d2);
}
}
tree.update(yPos1, removeKey(yMap.get(yPos1), x));
}
return res;
}
private int removeKey(TreeMap<Integer, Integer> map, int key) {
int tmp = map.get(key);
if (tmp == 1) {
map.remove(key);
} else {
map.put(key, tmp - 1);
}
return map.firstKey();
}
}
class SegmentTree {
private HashMap<Integer, Integer> ySort;
private int[] tree;
private int n;
public SegmentTree(HashMap<Integer, TreeMap<Integer, Integer>> yMap) {
if (!yMap.isEmpty()) {
ySort = getSortDistinct(yMap);
n = ySort.size();
tree = new int[n * 2];
buildTree(yMap);
}
}
private void buildTree(HashMap<Integer, TreeMap<Integer, Integer>> yMap) {
for (Map.Entry<Integer, TreeMap<Integer, Integer>> kv : yMap.entrySet()) {
tree[ySort.get(kv.getKey()) + n] = kv.getValue().firstKey();
}
for (int i = n - 1; i > 0; --i)
tree[i] = Math.min(tree[i * 2], tree[i * 2 + 1]);
}
public void update(int pos, int val) {
pos = ySort.get(pos) + n;
tree[pos] = val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
tree[pos / 2] = Math.min(tree[left], tree[right]);
pos /= 2;
}
}
public int minRange(int l, int r) {
l = ySort.get(l) + 1 + n;
r = ySort.get(r) - 1 + n;
int min = Integer.MAX_VALUE;
while (l <= r) {
if ((l % 2) == 1) {
min = Math.min(min, tree[l]);
l++;
}
if ((r % 2) == 0) {
min = Math.min(min, tree[r]);
r--;
}
l /= 2;
r /= 2;
}
return min;
}
private HashMap<Integer, Integer> getSortDistinct(HashMap<Integer, TreeMap<Integer, Integer>> yMap) {
List<Integer> arr = new ArrayList<>(yMap.keySet());
HashMap<Integer, Integer> ySort = new HashMap<>();
Collections.sort(arr);
for (int i = 0; i < arr.size(); ++i) {
ySort.put(arr.get(i), i);
}
return ySort;
}
}