class Solution {
public:
vector<int> numsGame(vector<int>& nums) {
}
};
LCP 24. 数字游戏
小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。
主办方请小扣回答出一个长度为 N 的数组，第 i 个元素(0 <= i < N)表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。回答正确方可进入秋日市集。
由于答案可能很大，请将每个最小操作数对 1,000,000,007 取余。
示例 1：
输入：
nums = [3,4,5,1,6,7]输出：
[0,0,0,5,6,7]解释： i = 0，[3] 无需操作 i = 1，[3,4] 无需操作； i = 2，[3,4,5] 无需操作； i = 3，将 [3,4,5,1] 操作成 [3,4,5,6], 最少 5 次操作； i = 4，将 [3,4,5,1,6] 操作成 [3,4,5,6,7], 最少 6 次操作； i = 5，将 [3,4,5,1,6,7] 操作成 [3,4,5,6,7,8]，最少 7 次操作； 返回 [0,0,0,5,6,7]。
示例 2：
输入：
nums = [1,2,3,4,5]输出：
[0,0,0,0,0]解释：对于任意计数器编号 i 都无需操作。
示例 3：
输入：
nums = [1,1,1,2,3,4]输出：
[0,1,2,3,3,3]解释： i = 0，无需操作； i = 1，将 [1,1] 操作成 [1,2] 或 [0,1] 最少 1 次操作； i = 2，将 [1,1,1] 操作成 [1,2,3] 或 [0,1,2]，最少 2 次操作； i = 3，将 [1,1,1,2] 操作成 [1,2,3,4] 或 [0,1,2,3]，最少 3 次操作； i = 4，将 [1,1,1,2,3] 操作成 [-1,0,1,2,3]，最少 3 次操作； i = 5，将 [1,1,1,2,3,4] 操作成 [-1,0,1,2,3,4]，最少 3 次操作； 返回 [0,1,2,3,3,3]。
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^3原站题解
rust 解法, 执行用时: 35 ms, 内存消耗: 3.9 MB, 提交时间: 2024-02-01 10:36:07
use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
pub fn nums_game(nums: Vec<i32>) -> Vec<i32> {
const MOD: i64 = 1_000_000_007;
let mut ans = vec![0; nums.len()];
let mut left = BinaryHeap::new(); // 维护较小的一半，大根堆
let mut right = BinaryHeap::new(); // 维护较大的一半，小根堆
let mut left_sum = 0i64;
let mut right_sum = 0i64;
for (i, &num) in nums.iter().enumerate() {
let mut b = num - i as i32;
if i % 2 == 0 { // 前缀长度是奇数
if let Some(&top) = left.peek() {
if b < top {
left_sum -= (top - b) as i64;
left.push(b);
b = left.pop().unwrap();
}
}
right_sum += b as i64;
right.push(Reverse(b));
ans[i] = ((right_sum - right.peek().unwrap().0 as i64 - left_sum) % MOD) as i32;
} else { // 前缀长度是偶数
let top = right.peek().unwrap().0;
if b > top {
right_sum += (b - top) as i64;
right.push(Reverse(b));
b = right.pop().unwrap().0;
}
left_sum += b as i64;
left.push(b);
ans[i] = ((right_sum - left_sum) % MOD) as i32;
}
}
ans
}
}
javascript 解法, 执行用时: 373 ms, 内存消耗: 80.6 MB, 提交时间: 2024-02-01 10:35:10
/**
* @param {number[]} nums
* @return {number[]}
*/
var numsGame = function (nums) {
const MOD = 1e9 + 7;
const ans = Array(nums.length);
const left = new MaxPriorityQueue(); // 维护较小的一半，大根堆
const right = new MinPriorityQueue(); // 维护较大的一半，小根堆
let leftSum = 0, rightSum = 0;
for (let i = 0; i < nums.length; i++) {
let b = nums[i] - i;
if (i % 2 === 0) { // 前缀长度是奇数
if (!left.isEmpty() && b < left.front().element) {
leftSum -= left.front().element - b;
left.enqueue(b);
b = left.dequeue().element;
}
rightSum += b;
right.enqueue(b);
ans[i] = (rightSum - right.front().element - leftSum) % MOD;
} else { // 前缀长度是偶数
if (b > right.front().element) {
rightSum += b - right.front().element;
right.enqueue(b);
b = right.dequeue().element;
}
leftSum += b;
left.enqueue(b);
ans[i] = (rightSum - leftSum) % MOD;
}
}
return ans;
};
golang 解法, 执行用时: 113 ms, 内存消耗: 9.1 MB, 提交时间: 2024-02-01 10:34:56
func numsGame(nums []int) []int {
const mod = 1_000_000_007
ans := make([]int, len(nums))
left := hp{} // 维护较小的一半，大根堆（小根堆取负号）
right := hp{} // 维护较大的一半，小根堆
for i, b := range nums {
b -= i
if i%2 == 0 {
heap.Push(&right, -left.pushPop(-b))
x := right.IntSlice[0] // 中位数
// 原本要减去 left.sum，但由于 left 所有元素都取负号，所以负负得正改为加法
ans[i] = (right.sum - x + left.sum) % mod
} else {
heap.Push(&left, -right.pushPop(b))
ans[i] = (right.sum + left.sum) % mod
}
}
return ans
}
type hp struct {
sort.IntSlice // 继承 Len, Less, Swap
sum int // 堆中元素之和
}
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)); h.sum += v.(int) }
func (hp) Pop() (_ any) { return } // 没用到，无需实现
// pushPop 先把 v 入堆，然后弹出并返回堆顶
// 如果 v <= 堆顶，则直接返回 v
func (h *hp) pushPop(v int) int {
if h.Len() > 0 && v > h.IntSlice[0] {
h.sum += v - h.IntSlice[0]
v, h.IntSlice[0] = h.IntSlice[0], v
heap.Fix(h, 0)
}
return v
}
cpp 解法, 执行用时: 109 ms, 内存消耗: 70.9 MB, 提交时间: 2024-02-01 10:34:39
class Solution {
public:
vector<int> numsGame(vector<int> &nums) {
const int MOD = 1'000'000'007;
vector<int> ans(nums.size());
priority_queue<int> left; // 维护较小的一半，大根堆
priority_queue<int, vector<int>, greater<int>> right; // 维护较大的一半，小根堆
long long left_sum = 0, right_sum = 0;
for (int i = 0; i < nums.size(); i++) {
int b = nums[i] - i;
if (i % 2 == 0) { // 前缀长度是奇数
if (!left.empty() && b < left.top()) {
left_sum -= left.top() - b;
left.push(b);
b = left.top();
left.pop();
}
right_sum += b;
right.push(b);
ans[i] = (right_sum - right.top() - left_sum) % MOD;
} else { // 前缀长度是偶数
if (b > right.top()) {
right_sum += b - right.top();
right.push(b);
b = right.top();
right.pop();
}
left_sum += b;
left.push(b);
ans[i] = (right_sum - left_sum) % MOD;
}
}
return ans;
}
};
java 解法, 执行用时: 71 ms, 内存消耗: 63.9 MB, 提交时间: 2024-02-01 10:34:26
class Solution {
public int[] numsGame(int[] nums) {
final int MOD = 1_000_000_007;
int[] ans = new int[nums.length];
PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a); // 维护较小的一半，大根堆
PriorityQueue<Integer> right = new PriorityQueue<>(); // 维护较大的一半，小根堆
long leftSum = 0, rightSum = 0;
for (int i = 0; i < nums.length; i++) {
int b = nums[i] - i;
if (i % 2 == 0) { // 前缀长度是奇数
if (!left.isEmpty() && b < left.peek()) {
leftSum -= left.peek() - b;
left.offer(b);
b = left.poll();
}
rightSum += b;
right.offer(b);
ans[i] = (int) ((rightSum - right.peek() - leftSum) % MOD);
} else { // 前缀长度是偶数
if (b > right.peek()) {
rightSum += b - right.peek();
right.offer(b);
b = right.poll();
}
leftSum += b;
left.offer(b);
ans[i] = (int) ((rightSum - leftSum) % MOD);
}
}
return ans;
}
}
python3 解法, 执行用时: 242 ms, 内存消耗: 34.6 MB, 提交时间: 2024-02-01 10:34:05
# 转换+中位数贪心+对顶堆
class Solution:
def numsGame(self, nums: List[int]) -> List[int]:
MOD = 1_000_000_007
ans = [0] * len(nums)
left = [] # 维护较小的一半，大根堆（小根堆取负号）
right = [] # 维护较大的一半，小根堆
left_sum = right_sum = 0
for i, b in enumerate(nums):
b -= i
if i % 2 == 0: # 前缀长度是奇数
left_sum -= max(-left[0] - b, 0) if left else 0
t = -heappushpop(left, -b)
right_sum += t
heappush(right, t)
ans[i] = (right_sum - right[0] - left_sum) % MOD
else: # 前缀长度是偶数
right_sum += max(b - right[0], 0)
t = heappushpop(right, b)
left_sum += t
heappush(left, -t)
ans[i] = (right_sum - left_sum) % MOD
return ans
python3 解法, 执行用时: 240 ms, 内存消耗: 38.1 MB, 提交时间: 2023-09-04 23:38:14
import heapq
class Solution:
def numsGame(self, nums: List[int]) -> List[int]:
nums = [nums[i] - i for i in range(len(nums))]
left_heap = [] #左侧为大根堆
right_heap = [] #右侧为小根堆
median = nums[0]
sl = 0
sr = 0
ret = [0] * len(nums)
for i in range(1, len(nums)):
if i%2 == 0:
#左右堆大小相等，现要再加入一元素
left_root = -left_heap[0]
right_root = right_heap[0]
if nums[i] < left_root:
median = left_root
heapq.heapreplace(left_heap, -nums[i])#由于heaqp是小根堆，存相反数来实现大根堆
sl = sl -left_root + nums[i]
elif nums[i] > right_root:
median = right_root
heapq.heapreplace(right_heap, nums[i])
sr = sr - right_root + nums[i]
else:
median = nums[i]
else:
if nums[i] > median:
heapq.heappush(right_heap, nums[i])
heapq.heappush(left_heap, -median)
sl += median
sr += nums[i]
else:
heapq.heappush(left_heap,-nums[i])
heapq.heappush(right_heap,median)
sl += nums[i]
sr += median
ret[i] = (sr - sl)%1000000007
return ret
cpp 解法, 执行用时: 112 ms, 内存消耗: 70.2 MB, 提交时间: 2023-09-04 23:37:08
class Solution {
private:
static constexpr int mod = 1000000007;
public:
vector<int> numsGame(vector<int>& nums) {
using LL = long long;
int n = nums.size();
if (n == 1) {
return {0};
}
for (int i = 0; i < n; ++i) {
nums[i] -= i;
}
priority_queue q0{less{}, vector{min(nums[0], nums[1])}};
priority_queue q1{greater{}, vector{max(nums[0], nums[1])}};
LL sum0 = q0.top(), sum1 = q1.top();
vector<int> ans = {0, static_cast<int>(sum1 - sum0)};
for (int i = 2; i < n; ++i) {
if (nums[i] <= q0.top()) {
q0.push(nums[i]);
sum0 += nums[i];
}
else {
q1.push(nums[i]);
sum1 += nums[i];
}
if (q0.size() == q1.size() + 2) {
int u = q0.top();
q0.pop();
sum0 -= u;
q1.push(u);
sum1 += u;
}
else if (q0.size() + 1 == q1.size()) {
int u = q1.top();
q1.pop();
sum1 -= u;
q0.push(u);
sum0 += u;
}
LL delta = (i & 1) ? sum1 - sum0 : sum1 - sum0 + q0.top();
ans.push_back(delta % mod);
}
return ans;
}
};