class Solution {
public:
long long minOperations(vector<int>& nums, int x, int k) {
}
};
3505. 使 K 个子数组内元素相等的最少操作数
给你一个整数数组 nums 和两个整数 x 和 k。你可以执行以下操作任意次（包括零次）：
nums 中的任意一个元素加 1 或减 1。返回为了使 nums 中 至少 包含 k 个长度 恰好 为 x 的不重叠子数组（每个子数组中的所有元素都相等）所需要的 最少 操作数。
子数组 是数组中连续、非空的一段元素。
示例 1：
输入： nums = [5,-2,1,3,7,3,6,4,-1], x = 3, k = 2
输出： 8
解释：
nums[1] 加 3；进行 2 次操作，将 nums[3] 减 2。得到的数组为 [5, 1, 1, 1, 7, 3, 6, 4, -1]。nums[5] 加 1；进行 2 次操作，将 nums[6] 减 2。得到的数组为 [5, 1, 1, 1, 7, 4, 4, 4, -1]。[1, 1, 1]（下标 1 到 3）和 [4, 4, 4]（下标 5 到 7）中的所有元素都相等。总共进行了 8 次操作，因此输出为 8。示例 2：
输入： nums = [9,-2,-2,-2,1,5], x = 2, k = 2
输出： 3
解释：
nums[4] 减 3。得到的数组为 [9, -2, -2, -2, -2, 5]。[-2, -2]（下标 1 到 2）和 [-2, -2]（下标 3 到 4）中的所有元素都相等。总共进行了 3 次操作，因此输出为 3。
提示：
2 <= nums.length <= 105-106 <= nums[i] <= 1062 <= x <= nums.length1 <= k <= 152 <= k * x <= nums.length原站题解
golang 解法, 执行用时: 397 ms, 内存消耗: 15.9 MB, 提交时间: 2025-04-03 09:48:26
func minOperations1(nums []int, x, k int) int64 {
n := len(nums)
dis := medianSlidingWindow(nums, x)
f := make([][]int, k+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= k; i++ {
f[i][i*x-1] = math.MaxInt
for j := i * x; j <= n-(k-i)*x; j++ { // 左右留出足够空间给其他子数组
f[i][j] = min(f[i][j-1], f[i-1][j-x]+dis[j-x]) // j-x 为子数组左端点
}
}
return int64(f[k][n])
}
// 空间优化
func minOperations(nums []int, x, k int) int64 {
n := len(nums)
dis := medianSlidingWindow(nums, x)
f := make([]int, n+1)
g := make([]int, n+1) // 滚动数组
for i := 1; i <= k; i++ {
g[i*x-1] = math.MaxInt
for j := i * x; j <= n-(k-i)*x; j++ {
g[j] = min(g[j-1], f[j-x]+dis[j-x])
}
f, g = g, f
}
return int64(f[n])
}
// 480. 滑动窗口中位数（有改动）
// 返回 nums 的所有长为 k 的子数组的（到子数组中位数的）距离和
func medianSlidingWindow(nums []int, k int) []int {
ans := make([]int, len(nums)-k+1)
left := newLazyHeap() // 最大堆（元素取反）
right := newLazyHeap() // 最小堆
for i, in := range nums {
// 1. 进入窗口
if left.size == right.size {
left.push(-right.pushPop(in))
} else {
right.push(-left.pushPop(-in))
}
l := i + 1 - k
if l < 0 { // 窗口大小不足 k
continue
}
// 2. 计算答案
v := -left.top()
s1 := v*left.size + left.sum // sum 取反
s2 := right.sum - v*right.size
ans[l] = s1 + s2
// 3. 离开窗口
out := nums[l]
if out <= -left.top() {
left.remove(-out)
if left.size < right.size {
left.push(-right.pop()) // 平衡两个堆的大小
}
} else {
right.remove(out)
if left.size > right.size+1 {
right.push(-left.pop()) // 平衡两个堆的大小
}
}
}
return ans
}
func newLazyHeap() *lazyHeap {
return &lazyHeap{removeCnt: map[int]int{}}
}
// 懒删除堆
type lazyHeap struct {
sort.IntSlice
removeCnt map[int]int // 每个元素剩余需要删除的次数
size int // 实际大小
sum int // 堆中元素总和
}
// 必须实现的两个接口
func (h *lazyHeap) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *lazyHeap) Pop() any { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
// 删除
func (h *lazyHeap) remove(v int) {
h.removeCnt[v]++ // 懒删除
h.size--
h.sum -= v
}
// 正式执行删除操作
func (h *lazyHeap) applyRemove() {
for h.removeCnt[h.IntSlice[0]] > 0 {
h.removeCnt[h.IntSlice[0]]--
heap.Pop(h)
}
}
// 查看堆顶
func (h *lazyHeap) top() int {
h.applyRemove()
return h.IntSlice[0]
}
// 出堆
func (h *lazyHeap) pop() int {
h.applyRemove()
h.size--
h.sum -= h.IntSlice[0]
return heap.Pop(h).(int)
}
// 入堆
func (h *lazyHeap) push(v int) {
if h.removeCnt[v] > 0 {
h.removeCnt[v]-- // 抵消之前的删除
} else {
heap.Push(h, v)
}
h.size++
h.sum += v
}
// push(v) 然后 pop()
func (h *lazyHeap) pushPop(v int) int {
if h.size > 0 && v > h.top() { // 最小堆，v 比堆顶大就替换堆顶
h.sum += v - h.IntSlice[0]
v, h.IntSlice[0] = h.IntSlice[0], v
heap.Fix(h, 0)
}
return v
}
cpp 解法, 执行用时: 883 ms, 内存消耗: 280.1 MB, 提交时间: 2025-04-03 09:47:36
template<typename T, typename Compare = less<T>>
class LazyHeap {
priority_queue<T, vector<T>, Compare> pq;
unordered_map<T, int> remove_cnt; // 每个元素剩余需要删除的次数
size_t sz = 0; // 实际大小
long long s = 0; // 堆中元素总和
// 正式执行删除操作
void apply_remove() {
while (!pq.empty() && remove_cnt[pq.top()] > 0) {
remove_cnt[pq.top()]--;
pq.pop();
}
}
public:
size_t size() {
return sz;
}
long long sum() {
return s;
}
// 删除
void remove(T x) {
remove_cnt[x]++; // 懒删除
sz--;
s -= x;
}
// 查看堆顶
T top() {
apply_remove();
return pq.top();
}
// 出堆
T pop() {
apply_remove();
T x = pq.top();
pq.pop();
sz--;
s -= x;
return x;
}
// 入堆
void push(T x) {
if (remove_cnt[x] > 0) {
remove_cnt[x]--; // 抵消之前的删除
} else {
pq.push(x);
}
sz++;
s += x;
}
// push(x) 然后 pop()
T push_pop(T x) {
apply_remove();
pq.push(x);
s += x;
x = pq.top();
pq.pop();
s -= x;
return x;
}
};
class Solution {
// 480. 滑动窗口中位数（有改动）
// 返回 nums 的所有长为 k 的子数组的（到子数组中位数的）距离和
vector<long long> medianSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> ans(n - k + 1);
LazyHeap<int> left; // 最大堆
LazyHeap<int, greater<int>> right; // 最小堆
for (int i = 0; i < n; i++) {
// 1. 进入窗口
int in = nums[i];
if (left.size() == right.size()) {
left.push(right.push_pop(in));
} else {
right.push(left.push_pop(in));
}
int l = i + 1 - k;
if (l < 0) { // 窗口大小不足 k
continue;
}
// 2. 计算答案
long long v = left.top();
long long s1 = v * left.size() - left.sum();
long long s2 = right.sum() - v * right.size();
ans[l] = s1 + s2;
// 3. 离开窗口
int out = nums[l];
if (out <= left.top()) {
left.remove(out);
if (left.size() < right.size()) {
left.push(right.pop()); // 平衡两个堆的大小
}
} else {
right.remove(out);
if (left.size() > right.size() + 1) {
right.push(left.pop()); // 平衡两个堆的大小
}
}
}
return ans;
}
public:
long long minOperations1(vector<int>& nums, int x, int k) {
int n = nums.size();
vector<long long> dis = medianSlidingWindow(nums, x);
vector f(k + 1, vector<long long>(n + 1));
for (int i = 1; i <= k; i++) {
f[i][i * x - 1] = LLONG_MAX;
for (int j = i * x; j <= n - (k - i) * x; j++) { // 左右留出足够空间给其他子数组
f[i][j] = min(f[i][j - 1], f[i - 1][j - x] + dis[j - x]); // j-x 为子数组左端点
}
}
return f[k][n];
}
// 空间优化
long long minOperations(vector<int>& nums, int x, int k) {
int n = nums.size();
vector<long long> dis = medianSlidingWindow(nums, x);
vector<long long> f(n + 1), g(n + 1); // 滚动数组
for (int i = 1; i <= k; i++) {
g[i * x - 1] = LLONG_MAX;
for (int j = i * x; j <= n - (k - i) * x; j++) {
g[j] = min(g[j - 1], f[j - x] + dis[j - x]);
}
swap(f, g);
}
return f[n];
}
};
java 解法, 执行用时: 797 ms, 内存消耗: 56.5 MB, 提交时间: 2025-04-03 09:46:55
class LazyHeap extends PriorityQueue<Integer> {
private final Map<Integer, Integer> removeCnt = new HashMap<>(); // 每个元素剩余需要删除的次数
private int size = 0; // 实际大小
private long sum = 0; // 堆中元素总和
public LazyHeap(Comparator<Integer> comparator) {
super(comparator);
}
public int size() {
return size;
}
public long sum() {
return sum;
}
// 删除
public void remove(int x) {
removeCnt.merge(x, 1, Integer::sum); // 懒删除
size--;
sum -= x;
}
// 正式执行删除操作
private void applyRemove() {
while (removeCnt.getOrDefault(peek(), 0) > 0) {
removeCnt.merge(poll(), -1, Integer::sum);
}
}
// 查看堆顶
public int top() {
applyRemove();
return peek();
}
// 出堆
public int pop() {
applyRemove();
size--;
sum -= peek();
return poll();
}
// 入堆
public void push(int x) {
int c = removeCnt.getOrDefault(x, 0);
if (c > 0) {
removeCnt.put(x, c - 1); // 抵消之前的删除
} else {
offer(x);
}
size++;
sum += x;
}
// push(x) 然后 pop()
public int pushPop(int x) {
applyRemove();
sum += x;
offer(x);
sum -= peek();
return poll();
}
}
class Solution {
public long minOperations1(int[] nums, int x, int k) {
int n = nums.length;
long[] dis = medianSlidingWindow(nums, x);
long[][] f = new long[k + 1][n + 1];
for (int i = 1; i <= k; i++) {
f[i][i * x - 1] = Long.MAX_VALUE;
for (int j = i * x; j <= n - (k - i) * x; j++) { // 左右留出足够空间给其他子数组
f[i][j] = Math.min(f[i][j - 1], f[i - 1][j - x] + dis[j - x]); // j-x 为子数组左端点
}
}
return f[k][n];
}
// 空间优化
public long minOperations(int[] nums, int x, int k) {
int n = nums.length;
long[] dis = medianSlidingWindow(nums, x);
long[] f = new long[n + 1];
long[] g = new long[n + 1]; // 滚动数组
for (int i = 1; i <= k; i++) {
g[i * x - 1] = Long.MAX_VALUE;
for (int j = i * x; j <= n - (k - i) * x; j++) {
g[j] = Math.min(g[j - 1], f[j - x] + dis[j - x]);
}
long[] tmp = f;
f = g;
g = tmp;
}
return f[n];
}
// 480. 滑动窗口中位数（有改动）
// 返回 nums 的所有长为 k 的子数组的（到子数组中位数的）距离和
private long[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length;
long[] ans = new long[n - k + 1];
LazyHeap left = new LazyHeap((a, b) -> Integer.compare(b, a)); // 最大堆
LazyHeap right = new LazyHeap(Integer::compare); // 最小堆
for (int i = 0; i < n; i++) {
// 1. 进入窗口
int in = nums[i];
if (left.size() == right.size()) {
left.push(right.pushPop(in));
} else {
right.push(left.pushPop(in));
}
int l = i + 1 - k;
if (l < 0) { // 窗口大小不足 k
continue;
}
// 2. 计算答案
long v = left.top();
long s1 = v * left.size() - left.sum();
long s2 = right.sum() - v * right.size();
ans[l] = s1 + s2;
// 3. 离开窗口
int out = nums[l];
if (out <= left.top()) {
left.remove(out);
if (left.size() < right.size()) {
left.push(right.pop()); // 平衡两个堆的大小
}
} else {
right.remove(out);
if (left.size() > right.size() + 1) {
right.push(left.pop()); // 平衡两个堆的大小
}
}
}
return ans;
}
}
python3 解法, 执行用时: 2895 ms, 内存消耗: 44.2 MB, 提交时间: 2025-04-03 09:45:36
class LazyHeap:
def __init__(self):
self.heap = []
self.remove_cnt = defaultdict(int) # 每个元素剩余需要删除的次数
self.size = 0 # 实际大小
self.sum = 0 # 堆中元素总和
# 删除
def remove(self, x: int) -> None:
self.remove_cnt[x] += 1 # 懒删除
self.size -= 1
self.sum -= x
# 正式执行删除操作
def apply_remove(self) -> None:
while self.heap and self.remove_cnt[self.heap[0]] > 0:
self.remove_cnt[self.heap[0]] -= 1
heappop(self.heap)
# 查看堆顶
def top(self) -> int:
self.apply_remove()
return self.heap[0]
# 出堆
def pop(self) -> int:
self.apply_remove()
self.size -= 1
self.sum -= self.heap[0]
return heappop(self.heap)
# 入堆
def push(self, x: int) -> None:
if self.remove_cnt[x] > 0:
self.remove_cnt[x] -= 1 # 抵消之前的删除
else:
heappush(self.heap, x)
self.size += 1
self.sum += x
# push(x) 然后 pop()
def pushpop(self, x: int) -> int:
self.apply_remove()
if not self.heap or x <= self.heap[0]:
return x
self.sum += x - self.heap[0]
return heappushpop(self.heap, x)
class Solution:
# 480. 滑动窗口中位数（有改动）
# 返回 nums 的所有长为 k 的子数组的（到子数组中位数的）距离和
def medianSlidingWindow(self, nums: list[int], k: int) -> list[int]:
ans = [0] * (len(nums) - k + 1)
left = LazyHeap() # 最大堆（元素取反）
right = LazyHeap() # 最小堆
for i, x in enumerate(nums):
# 1. 进入窗口
if left.size == right.size:
left.push(-right.pushpop(x))
else:
right.push(-left.pushpop(-x))
l = i + 1 - k
if l < 0: # 窗口大小不足 k
continue
# 2. 计算答案
v = -left.top()
s1 = v * left.size + left.sum # sum 取反
s2 = right.sum - v * right.size
ans[l] = s1 + s2
# 3. 离开窗口
x = nums[l]
if x <= -left.top():
left.remove(-x)
if left.size < right.size:
left.push(-right.pop()) # 平衡两个堆的大小
else:
right.remove(x)
if left.size > right.size + 1:
right.push(-left.pop()) # 平衡两个堆的大小
return ans
# 空间优化
def minOperations(self, nums: List[int], x: int, k: int) -> int:
n = len(nums)
dis = self.medianSlidingWindow(nums, x)
f = [0] * (n + 1)
g = [0] * (n + 1) # 滚动数组
for i in range(1, k + 1):
g[i * x - 1] = inf
for j in range(i * x, n - (k - i) * x + 1):
g[j] = min(g[j - 1], f[j - x] + dis[j - x])
f, g = g, f
return f[n]
python3 解法, 执行用时: 3207 ms, 内存消耗: 44.9 MB, 提交时间: 2025-04-03 09:44:58
class LazyHeap:
def __init__(self):
self.heap = []
self.remove_cnt = defaultdict(int) # 每个元素剩余需要删除的次数
self.size = 0 # 实际大小
self.sum = 0 # 堆中元素总和
# 删除
def remove(self, x: int) -> None:
self.remove_cnt[x] += 1 # 懒删除
self.size -= 1
self.sum -= x
# 正式执行删除操作
def apply_remove(self) -> None:
while self.heap and self.remove_cnt[self.heap[0]] > 0:
self.remove_cnt[self.heap[0]] -= 1
heappop(self.heap)
# 查看堆顶
def top(self) -> int:
self.apply_remove()
return self.heap[0]
# 出堆
def pop(self) -> int:
self.apply_remove()
self.size -= 1
self.sum -= self.heap[0]
return heappop(self.heap)
# 入堆
def push(self, x: int) -> None:
if self.remove_cnt[x] > 0:
self.remove_cnt[x] -= 1 # 抵消之前的删除
else:
heappush(self.heap, x)
self.size += 1
self.sum += x
# push(x) 然后 pop()
def pushpop(self, x: int) -> int:
self.apply_remove()
if not self.heap or x <= self.heap[0]:
return x
self.sum += x - self.heap[0]
return heappushpop(self.heap, x)
class Solution:
# 480. 滑动窗口中位数（有改动）
# 返回 nums 的所有长为 k 的子数组的（到子数组中位数的）距离和
def medianSlidingWindow(self, nums: list[int], k: int) -> list[int]:
ans = [0] * (len(nums) - k + 1)
left = LazyHeap() # 最大堆（元素取反）
right = LazyHeap() # 最小堆
for i, x in enumerate(nums):
# 1. 进入窗口
if left.size == right.size:
left.push(-right.pushpop(x))
else:
right.push(-left.pushpop(-x))
l = i + 1 - k
if l < 0: # 窗口大小不足 k
continue
# 2. 计算答案
v = -left.top()
s1 = v * left.size + left.sum # sum 取反
s2 = right.sum - v * right.size
ans[l] = s1 + s2
# 3. 离开窗口
x = nums[l]
if x <= -left.top():
left.remove(-x)
if left.size < right.size:
left.push(-right.pop()) # 平衡两个堆的大小
else:
right.remove(x)
if left.size > right.size + 1:
right.push(-left.pop()) # 平衡两个堆的大小
return ans
def minOperations(self, nums: List[int], x: int, k: int) -> int:
n = len(nums)
dis = self.medianSlidingWindow(nums, x)
f = [[0] * (n + 1) for _ in range(k + 1)]
for i in range(1, k + 1):
f[i][i * x - 1] = inf
for j in range(i * x, n - (k - i) * x + 1): # 左右留出足够空间给其他子数组
f[i][j] = min(f[i][j - 1], f[i - 1][j - x] + dis[j - x]) # j-x 为子数组左端点
return f[k][n]