You are monitoring building density in a district of N positions (0..N-1), all initially occupied. queries is a sequence of positions to demolish (in order). After each removal, return the longest contiguous run of still-occupied positions as a list of those positions; ties broken by leftmost.
Example: N=5, queries=[2, 1, 3] → [[0, 1], [0, 1], [4]].
解法
用有序集合维护占用位置；每次移除后扫一遍有序位置找最长连续段。暴力 O(Q · N) 在 N, Q ≤ 10⁵ 下足够。
def longestSegmentsAfterQueries(N: int, queries: list[int]) -> list[list[int]]:
available = set(range(N))
results = []
for q in queries:
available.discard(q)
best_len, best_start = 0, -1
cur_len, cur_start = 0, -1
for p in sorted(available):
if cur_start != -1 and p == cur_start + cur_len:
cur_len += 1
else:
cur_len, cur_start = 1, p
if cur_len > best_len:
best_len, best_start = cur_len, cur_start
results.append(list(range(best_start, best_start + best_len)) if best_len > 0 else [])
return resultsimport java.util.*;
class Solution {
static List<List<Integer>> longestSegmentsAfterQueries(int N, int[] queries) {
TreeSet<Integer> available = new TreeSet<>();
for (int i = 0; i < N; i++) available.add(i);
List<List<Integer>> results = new ArrayList<>();
for (int q : queries) {
available.remove(q);
int bestLen = 0, bestStart = -1, curLen = 0, curStart = -1;
Integer prev = null;
for (int p : available) {
if (prev != null && p == prev + 1) curLen++;
else { curLen = 1; curStart = p; }
if (curLen > bestLen) { bestLen = curLen; bestStart = curStart; }
prev = p;
}
List<Integer> seg = new ArrayList<>();
for (int i = 0; i < bestLen; i++) seg.add(bestStart + i);
results.add(seg);
}
return results;
}
}#include <vector>
#include <set>
using namespace std;
vector<vector<int>> longestSegmentsAfterQueries(int N, vector<int>& queries) {
set<int> available;
for (int i = 0; i < N; i++) available.insert(i);
vector<vector<int>> results;
for (int q : queries) {
available.erase(q);
int bestLen = 0, bestStart = -1, curLen = 0, curStart = -1;
bool hasPrev = false; int prev = 0;
for (int p : available) {
if (hasPrev && p == prev + 1) curLen++;
else { curLen = 1; curStart = p; }
if (curLen > bestLen) { bestLen = curLen; bestStart = curStart; }
prev = p; hasPrev = true;
}
vector<int> seg;
for (int i = 0; i < bestLen; i++) seg.push_back(bestStart + i);
results.push_back(seg);
}
return results;
}Given an array numbers of length n and a positive integer k, find the number of contiguous subarrays for which there are at least k pairs of elements with duplicate values. A pair (i, j) with i < j is counted if numbers[i] == numbers[j].
Examples:
numbers = [0, 1, 0, 1, 0], k = 2→3numbers = [2, 2, 2, 2, 2, 2], k = 3→1
解法
滑动窗口：右扩时把 cnt[x] 个新重复对加进 dup_pairs；dup_pairs ≥ k 时收缩左端(先减 cnt[numbers[l]] 抵消贡献的对数)。收缩后以 r 结尾、起点在 [0..l-1] 的子数组都合法，ans += l。复杂度 O(n)。
from collections import defaultdict
def countSubarrays(numbers: list[int], k: int) -> int:
cnt = defaultdict(int)
dup_pairs = 0
l = 0
ans = 0
for r in range(len(numbers)):
x = numbers[r]
dup_pairs += cnt[x]
cnt[x] += 1
while dup_pairs >= k:
cnt[numbers[l]] -= 1
dup_pairs -= cnt[numbers[l]]
l += 1
ans += l
return ansimport java.util.*;
class Solution {
static long countSubarrays(int[] numbers, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
long dup = 0, ans = 0;
int l = 0;
for (int r = 0; r < numbers.length; r++) {
int x = numbers[r];
dup += cnt.getOrDefault(x, 0);
cnt.merge(x, 1, Integer::sum);
while (dup >= k) {
cnt.merge(numbers[l], -1, Integer::sum);
dup -= cnt.get(numbers[l]);
l++;
}
ans += l;
}
return ans;
}
}#include <vector>
#include <unordered_map>
using namespace std;
long long countSubarrays(vector<int>& numbers, int k) {
unordered_map<int, int> cnt;
long long dup = 0, ans = 0;
int l = 0;
for (int r = 0; r < (int)numbers.size(); r++) {
int x = numbers[r];
dup += cnt[x];
cnt[x]++;
while (dup >= k) {
cnt[numbers[l]]--;
dup -= cnt[numbers[l]];
l++;
}
ans += l;
}
return ans;
}A rhombic area of size r is the set of all cells whose Manhattan distance to a center cell is less than r. Given a rectangular matrix of integers matrix and an integer radius, for each cell c whose rhombic area of size radius fully fits within the matrix, sum the elements within that rhombus. Return the highest sum. Return 0 if no center fits.
Example: matrix = 6×6 grid of values, radius = 3 → highest rhombus sum (e.g. 35).
解法
枚举每个候选中心 (cr, cc)(菱形不越界)，再遍历每格 (i, j)，把 |cr - i| + |cc - j| < r 的累加。最坏 O(n²m²)，小网格无压力。
def maxRhombicSum(matrix: list[list[int]], radius: int) -> int:
n, m = len(matrix), len(matrix[0])
best = 0
found = False
for cr in range(radius - 1, n - radius + 1):
for cc in range(radius - 1, m - radius + 1):
s = 0
for i in range(n):
for j in range(m):
if abs(cr - i) + abs(cc - j) < radius:
s += matrix[i][j]
if not found or s > best:
best = s; found = True
return bestclass Solution {
static long maxRhombicSum(int[][] matrix, int radius) {
int n = matrix.length, m = matrix[0].length;
long best = 0;
boolean found = false;
for (int cr = radius - 1; cr < n - radius + 1; cr++)
for (int cc = radius - 1; cc < m - radius + 1; cc++) {
long s = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (Math.abs(cr - i) + Math.abs(cc - j) < radius) s += matrix[i][j];
if (!found || s > best) { best = s; found = true; }
}
return best;
}
}#include <vector>
#include <cstdlib>
using namespace std;
long long maxRhombicSum(vector<vector<int>>& matrix, int radius) {
int n = matrix.size(), m = matrix[0].size();
long long best = 0;
bool found = false;
for (int cr = radius - 1; cr < n - radius + 1; cr++)
for (int cc = radius - 1; cc < m - radius + 1; cc++) {
long long s = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (abs(cr - i) + abs(cc - j) < radius) s += matrix[i][j];
if (!found || s > best) { best = s; found = true; }
}
return best;
}