目录
一，3379. 转换数组
本题就是一个模拟题，难点在于如何计算循环数组移动之后的下标，可以模拟循环，遇到-1转成n-1，遇到 n 转成 0，或者直接使用模运算。
代码如下：
class Solution {
public int[] constructTransformedArray(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
for(int i=0; i<n; i++){
int j = (nums[i]%n + i + n) % n;
ans[i] = nums[j];
}
return ans;
}
}二，3380. 用点构造面积最大的矩形 I
本题数据范围小，直接暴力枚举，代码如下：
class Solution {
//(x,y) (a,b) (x,b) (a,y)
public record Data(int x, int y){
}
public boolean check(int i, int j, int[][] p){
int cnt = 0;
for(int[] t : p){
int x = t[0], y = t[1];
if(x >= Math.min(p[i][0], p[j][0]) && x <= Math.max(p[i][0], p[j][0]) && y >= Math.min(p[i][1], p[j][1]) && y <= Math.max(p[i][1], p[j][1]))
cnt += 1;
}
return cnt == 4;
}
public int maxRectangleArea(int[][] p) {
int n = p.length;
Set<Data> set = new HashSet<>();
for(int i=0; i<n; i++){
set.add(new Data(p[i][0], p[i][1]));
}
int ans = -1;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
Data d1 = new Data(p[i][0], p[j][1]);
Data d2 = new Data(p[j][0], p[i][1]);
if(p[i][0] != p[j][0] && p[i][1] != p[j][1] && set.contains(d1) && set.contains(d2) && check(i, j, p)){
ans = Math.max(ans, Math.abs(p[i][0]-p[j][0]) * Math.abs(p[i][1]-p[j][1]));
}
}
}
return ans;
}
}三，3381. 长度可被 K 整除的子数组的最大元素和
本题看到子数组的最大和，第一时间想到的是滑动窗口，但是题目还要求子数组的长度可以被 k 整除，所以如果使用滑动窗口就需要枚举窗口的大小即 k 及其倍数，但是这样做时间复杂度为O(n^2/k)，必然会超时。
再看题目求子数组的和，子数组和可以用前缀和(suf)来求，假设子数组的区间为 [L，R] 且 R - L + 1 是 k 的倍数，枚举子数组的右端点R，要求 suf[R] - suf[L-1] 的最大值 (L-1 = [R - ?*k，...，R - 2*k，R - k])，就是求 suf[L-1] (L-1 = [R - ?*k，...，R - 2*k，R - k]) 的最小值。因为是从小到大枚举nums数组，所以可以一边枚举，一边计算 min(suf[L-1])。画个图理解一下：
代码如下:
class Solution {
public long maxSubarraySum(int[] nums, int k) {
long ans = Long.MIN_VALUE;
int n = nums.length;
long[] suf = new long[n+1];
long[] pre = new long[k];
Arrays.fill(pre, Long.MAX_VALUE/2);
for(int i=0; i<n; i++){
suf[i+1] = suf[i] + nums[i];
}
for(int i=0; i<=n; i++){
ans = Math.max(ans, suf[i] - pre[i%k]);
pre[i%k] = Math.min(pre[i%k], suf[i]);
}
return ans;
}
}四，3382. 用点构造面积最大的矩形 II
class Solution {
//树状数组
static class Fenwick{
int[] f;
public Fenwick(int n){
f = new int[n];
}
void add(int i){
while(i < f.length){
f[i] += 1;
i += i & -i;
}
}
int pre(int i){
int res = 0;
while(i > 0){
res += f[i];
i -= i & -i;
}
return res;
}
int query(int l, int r){
return pre(r) - pre(l-1);
}
}
//左下角右上角(x1,y1) (x2,y2) 面积area
private record Query(int x1, int x2, int y1, int y2, long area){
}
//qid：记录是那个区域的查询，一个区域有两个查询[0,x1-1] - [0, x2] : [y1, y2]
//sign：记录是当前区域内查询的加减操作
//[y1,y2]：是[0,x] - [y1,y2]的区域查询
private record Data(int qid, int sign, int y1, int y2){
}
public long maxRectangleArea(int[] xCoord, int[] yCoord) {
Map<Integer, List<Integer>> xMap = new HashMap<>();//(x,[y1,y2,y3...])
Map<Integer, List<Integer>> yMap = new HashMap<>();//(y,[x1,x2,x3...])
int n = xCoord.length;
for(int i=0; i<n; i++) {
xMap.computeIfAbsent(xCoord[i], k->new ArrayList<>()).add(yCoord[i]);
yMap.computeIfAbsent(yCoord[i], k->new ArrayList<>()).add(xCoord[i]);
}
//(x,y1)的相邻下面一个点(x,y2)
Map<Long, Integer> below = new HashMap<>();
for(var e : xMap.entrySet()){
int x = e.getKey();
List<Integer> ys = e.getValue();
ys.sort(null);
for(int i=1; i<ys.size(); i++){
below.put((long)x<<32|ys.get(i), ys.get(i-1));
}
}
//(x1,y)的相邻左边一个点(x2,y)
Map<Long, Integer> left = new HashMap<>();
for(var e : yMap.entrySet()){
int y = e.getKey();
List<Integer> xs = e.getValue();
xs.sort(null);
for(int i=1; i<xs.size(); i++){
left.put((long)xs.get(i)<<32|y, xs.get(i-1));
}
}
//方便离散化
List<Integer> xs = new ArrayList<>(xMap.keySet());
List<Integer> ys = new ArrayList<>(yMap.keySet());
xs.sort(null);
ys.sort(null);
//统计满足条件(即是矩形)的左下角(x1,y1)右上角(x2,y2)
List<Query> queries = new ArrayList<>();
for(var e : xMap.entrySet()){
int x2 = e.getKey();
List<Integer> listY = e.getValue();
for(int i=1; i<listY.size(); i++){
int y2 = listY.get(i);
int x1 = left.getOrDefault((long)x2<<32|y2, -1);
if(x1 < 0) continue;
int y1 = listY.get(i-1);
//判断(x2,y1)和(x1,y1)相邻
if(left.getOrDefault((long)x2<<32|y1, -1) != x1)
continue;
//判断(x1,y2)和(x1,y1)相邻
if(below.getOrDefault((long)x1<<32|y2, -1) != y1)
continue;
queries.add(new Query(
Collections.binarySearch(xs, x1),
Collections.binarySearch(xs, x2),
Collections.binarySearch(ys, y1),
Collections.binarySearch(ys, y2),
(long)(x2-x1)*(y2-y1)
));
}
}
//添加二维查询 - 一块区域需要两个查询[0,x1-1] - [0, x2] : [y1, y2]
List<Data>[] qs = new ArrayList[xs.size()];
Arrays.setAll(qs, i -> new ArrayList<>());
for(int i=0; i<queries.size(); i++){
Query q = queries.get(i);
if(q.x1 > 0){//[0,x1-1] : [y1, y2]
qs[q.x1-1].add(new Data(i, -1, q.y1, q.y2));
}
//[0, x2] : [y1, y2]
qs[q.x2].add(new Data(i, 1, q.y1, q.y2));
}
int[] res = new int[queries.size()];
Fenwick tree = new Fenwick(ys.size()+1);//[1,n]
for(int i=0; i<xs.size(); i++){
for(int y : xMap.get(xs.get(i))){
tree.add(Collections.binarySearch(ys, y)+1);
}
for(Data q : qs[i]){
res[q.qid] += q.sign * tree.query(q.y1+1, q.y2+1);
}
}
long ans = -1;
for(int i=0; i<res.length; i++){
if(res[i] == 4)
ans = Math.max(ans, queries.get(i).area);
}
return ans;
}
}