2022-09-05:作为国王的统治者,你有一支巫师军队听你指挥。:给你一个下标从 0 开始的整数数组 strength ,其中
数组 一个 2022 开始 作为 整数 09 其中
2023-06-13 09:14:40 时间
2022-09-05:作为国王的统治者,你有一支巫师军队听你指挥。
:给你一个下标从 0 开始的整数数组 strength ,
其中 strength[i] 表示第 i 位巫师的力量值。
对于连续的一组巫师(也就是这些巫师的力量值是 strength 的 子数组),
总力量 定义为以下两个值的 乘积 :
巫师中 最弱 的能力值 * 组中所有巫师的个人力量值 之和 。
请你返回 所有 巫师组的 总 力量之和。由于答案可能很大,请将答案对 109 + 7 取余 后返回。
子数组 是一个数组里 非空 连续子序列。
答案2022-09-05:
单调栈。
代码用rust编写。代码如下:
fn main() {
let mut arr = vec![1, 3, 1, 2];
let ans = total_strength(&mut arr);
println!("ans = {}", ans);
}
const mod0: i64 = 1000000007;
fn total_strength(arr: &mut Vec<i32>) -> i32 {
let n = arr.len() as i32;
let mut pre_sum = arr[0] as i64;
let mut sum_sum: Vec<i64> = vec![];
for _ in 0..n {
sum_sum.push(0);
}
sum_sum[0] = arr[0] as i64;
for i in 1..n {
pre_sum += arr[i as usize] as i64;
sum_sum[i as usize] = (sum_sum[(i - 1) as usize] + pre_sum) % mod0;
}
let mut stack: Vec<i32> = vec![];
for _ in 0..n {
stack.push(0);
}
let mut size: i32 = 0;
let mut ans: i64 = 0;
for i in 0..n {
while size > 0 && arr[stack[(size - 1) as usize] as usize] >= arr[i as usize] {
size -= 1;
let m = stack[size as usize];
let l = if size > 0 {
stack[(size - 1) as usize]
} else {
-1
};
// l(<当前值,且最近,到不了) m(当前数,做为最小值) i(<=当前数,到不了的!)
ans += magic_sum(arr, &mut sum_sum, l, m, i);
ans %= mod0;
}
stack[size as usize] = i;
size += 1;
}
while size > 0 {
size -= 1;
let m = stack[size as usize];
let l = if size > 0 {
stack[(size - 1) as usize]
} else {
-1
};
ans += magic_sum(arr, &mut sum_sum, l, m, n);
ans %= mod0;
}
ans as i32
}
fn magic_sum(arr: &mut Vec<i32>, sum_sum: &mut Vec<i64>, l: i32, m: i32, r: i32) -> i64 {
let left = (m as i64 - l as i64)
* (sum_sum[(r - 1) as usize]
- if m - 1 >= 0 {
sum_sum[(m - 1) as usize]
} else {
0
}
+ mod0)
% mod0;
let right = (r as i64 - m as i64)
* (if m - 1 >= 0 {
sum_sum[(m - 1) as usize]
} else {
0
} - if l - 1 >= 0 {
sum_sum[(l - 1) as usize]
} else {
0
} + mod0)
% mod0;
return arr[m as usize] as i64 * ((left - right + mod0) % mod0);
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_06_2_week/Code02_SumOfTotalStrengthOfWizards.java)
相关文章
- 2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组, 求剩下的数组,严格连续递增的子数组最大长度。 n <= 10^6。 来自字节。
- 2022-10-19:一个数组如果满足 : 升降升降升降... 或者 降升降升...都是满足的 给定一个数组, 1,看有几种方法能够剔除一个元素,达成上述的要求
- 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
- 2023-03-02:给定一个数组arr,长度为n, 任意相邻的两个数里面至少要有一个被选出来,组成子序列,才是合法的! 求所有可能的合法子序列中,最大中位数是
- 2022-12-16:给你一个长度为n的数组,并询问q次 每次询问区间[l,r]之间是否存在小于等于k个数的和大于等于x 每条查询返回true或者false。
- 2023-01-14:给定一个二维数组map,代表一个餐厅,其中只有0、1两种值 map[i][j] == 0 表示(i,j)位置是空座 map[i][j] =
- 2022-11-03:给定一个数组arr,和一个正数k如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号,而且可
- 2022-12-16:给你一个长度为n的数组,并询问q次每次询问区间[l,r]之间是否存在小于等于k个数的和大于等于x每条查询返
- 2022-12-18:给定一个长度为n的二维数组graph,代表一张图,graph[i] = {a,b,c,d} 表示i讨厌(a
- 2023-01-06:给定一个只由小写字母组成的字符串str,长度为N,给定一个只由0、1组成的数组arr,长度为N,arr[i
- PHP 二维关联数组根据其中一个字段排序
- 【力扣/牛客刷题】189. 轮转数组
- 2023-04-19:给定一个非负数组arr 任何两个数差值的绝对值,如果arr中没有,都要加入到arr里 然后新的arr继续,任何两个数差值的绝对值,如果ar
- PHP array_fill():以填充数据的方式创建新数组
- 用js实现随机返回数组的一个元素