2025-01-19:数组中的峰值。用go语言，在一个整数数组 nums 中，若
2025-01-19：数组中的峰值。用go语言，在一个整数数组 nums 中，若某个元素大于其左右相邻的元素，则称该元素为“峰值”元素。
你会得到一个整数数组 nums 和一个二维数组 queries。需要处理两种操作：
1.queries[i] = [1, li, ri]：计算子数组 nums[li..ri] 中的峰值元素数量。
2.queries[i] = [2, indexi, vali]：将 nums[indexi] 的值更改为 vali。
最终，你需要返回一个数组 answer，其中依次包含了每一次第一种操作的结果。
请注意，子数组的第一个和最后一个元素不被视为峰值元素。
3 <= nums.length <= 100000。
1 <= nums[i] <= 100000。
1 <= queries.length <= 100000。
queries[i][0] == 1 或者 queries[i][0] == 2。
对于所有的 i ，都有：
queries[i][0] == 1 ：0 <= queries[i][1] <= queries[i][2] <= nums.length - 1。
queries[i][0] == 2 ：0 <= queries[i][1] <= nums.length - 1, 1 <= queries[i][2] <= 100000。
输入：nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]。
输出：[0,1]。
解释：
第一个操作：nums[2] 变为 4 ，它已经是 4 了，所以保持不变。
第二个操作：[4,1,4] 中峰值元素的数目为 0 。
第三个操作：第二个 4 是 [4,1,4,2,1] 中的峰值元素。
答案2025-01-19：
chatgpt[1]
题目来自leetcode3187。
大体步骤如下：
1.定义峰值：
- ? 一个元素 nums[i] 被认为是峰值元素，当且仅当 nums[i] 大于相邻的两个元素 nums[i-1] 和 nums[i+1]，即 nums[i] > nums[i-1] 且 nums[i] > nums[i+1]。
2.初始化 Fenwick Tree：
- ? 创建一个 Fenwick Tree (称为 f)，其大小为 n-1，用于存储可能的峰值数量。
- ? 在树的初始化阶段，遍历 nums 数组，检查 nums[i] 是否为峰值，若是，则在 Fenwick Tree 中更新相应的值。
3.查询操作：
- ? 当处理 queries[i] = [1, li, ri] 的查询时，使用 Fenwick Tree 的 query 方法计算 li 到 ri 的子数组中峰值的数量。
- ? 注意，只有子数组的 li 和 ri 之间的元素（不包括边界元素）将被视为可能的峰值。
4.更新操作：
- ? 当处理 queries[i] = [2, index, value] 的更新操作时，需要将 nums[index] 更新为 value。
- ? 在更新之前，需要检查 index 左边的 index-1 和右边的 index+1 元素是否会影响已有的峰值。如果 nums[index-1] 和 nums[index+1] 与 nums[index] 的新值不再符合峰值的条件，则在 Fenwick Tree 中对应减去峰值数量。
- ? 执行更新后，再次检查更新后的 nums[index-1] 和 nums[index+1]，如果新的值符合峰值条件，则在 Fenwick Tree 中对应增加峰值数量。
5.返回结果：
- ? 所有查询类型为 1 的结果将被存储在列表中，最后返回该列表作为输出。
时间复杂度
- ? 初始化阶段：遍历 nums 的长度为 n，每次更新 Fenwick Tree 最多需 O(log n) 的时间。初始化的时间复杂度为 O(n log n)。
- ? 每个查询操作（类型 1）：也是 O(log n)，因此如果有 q 个此类请求，总的时间复杂度是 O(q log n)。
- ? 更新操作（类型 2）同样是 O(log n)，因此如果有 q 个此类请求，总的时间复杂度也是 O(q log n)。
综上所述，综合处理所有的操作，总的时间复杂度为：O(n log n)+O(q log n)。
空间复杂度
- ? 使用了一个 Fenwick Tree 数组，大小为 n-1，因此额外空间复杂度为 O(n)。
- ? 由于我们只用了少量额外的变量，整体的空间复杂度依旧为 O(n)。
总结
- ? 时间复杂度：O(n log n + q log n)
- ? 空间复杂度：O(n)
Go完整代码如下：
package main
import (
"fmt"
)
type fenwick []int
func (f fenwick) update(i, val int) {
for ; i < len(f); i += i & -i {
f[i] += val
}
}
func (f fenwick) pre(i int) (res int) {
for ; i > 0; i &= i - 1 {
res += f[i]
}
return res
}
func (f fenwick) query(l, r int) int {
if r < l {
return 0
}
return f.pre(r) - f.pre(l-1)
}
func countOfPeaks(nums []int, queries [][]int) (ans []int) {
n := len(nums)
f := make(fenwick, n-1)
update := func(i, val int) {
if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
f.update(i, val)
}
}
for i := 1; i < n-1; i++ {
update(i, 1)
}
for _, q := range queries {
if q[0] == 1 {
ans = append(ans, f.query(q[1]+1, q[2]-1))
continue
}
i := q[1]
for j := max(i-1, 1); j <= min(i+1, n-2); j++ {
update(j, -1)
}
nums[i] = q[2]
for j := max(i-1, 1); j <= min(i+1, n-2); j++ {
update(j, 1)
}
}
return
}
func main() {
nums := []int{4,1,4,2,1,5}
queries := [][]int{{2,2,4},{1,0,2},{1,0,4}}
result := countOfPeaks(nums,queries)
fmt.Println(result)
}
在这里插入图片描述
Rust完整代码如下：
struct Fenwick {
tree: Vec,
}
impl Fenwick {
fn new(size: usize) -> Self {
Fenwick {
tree: vec![0; size + 1],
}
}
fn update(&mut self, index: usize, value: i32) {
let mut i = index as isize;
while i < self.tree.len() as isize {
self.tree[i as usize] += value;
i += i & -i;
}
}
fn pre(&self, index: usize) -> i32 {
let mut res = 0;
let mut i = index as isize;
while i > 0 {
res += self.tree[i as usize];
i &= i - 1;
}
res
}
fn query(&self, left: usize, right: usize) -> i32 {
if right < left {
return 0;
}
self.pre(right) - self.pre(left - 1)
}
}
fn count_of_peaks(nums: &mut Vec, queries: Vec>) -> Vec {
let n = nums.len();
let mut f = Fenwick::new(n - 1);
fn update_peak(f: &mut Fenwick, nums: &[i32], i: usize, val: i32) {
if i > 0 && i < nums.len() - 1 {
if nums[i - 1] < nums[i] && nums[i] > nums[i + 1] {
f.update(i, val);
}
}
}
for i in 1..(n - 1) {
update_peak(&mut f, nums, i, 1);
}
let mut ans = Vec::new();
for q in queries {
if q[0] == 1 {
ans.push(f.query((q[1] + 1) as usize, (q[2] - 1) as usize));
} else {
let i = q[1] as usize;
for j in max(i as isize - 1, 1) as usize..=min(i + 1, n - 2) {
update_peak(&mut f, nums, j, -1);
}
nums[i] = q[2];
for j in max(i as isize - 1, 1) as usize..=min(i + 1, n - 2) {
update_peak(&mut f, nums, j, 1);
}
}
}
ans
}
fn main() {
let mut nums = vec![4, 1, 4, 2, 1, 5];
let queries = vec![vec![2, 2, 4], vec![1, 0, 2], vec![1, 0, 4]];
let result = count_of_peaks(&mut nums, queries);
println!("{:?}", result);
}
// 輔助函數
fn max(a: isize, b: isize) -> isize {
if a > b {
a
} else {
b
}
}
fn min(a: usize, b: usize) -> usize {
if a < b {
a
} else {
b
}
}
在这里插入图片描述
C完整代码如下：
#include
#include
typedef struct {
int *tree;
int size;
} Fenwick;
void fenwick_init(Fenwick *f, int size) {
f->size = size + 1; // 使用1-based索引
f->tree = (int *)calloc(f->size, sizeof(int));
}
void fenwick_update(Fenwick *f, int index, int value) {
for (; index < f->size; index += index & -index) {
f->tree[index] += value;
}
}
int fenwick_pre(Fenwick *f, int index) {
int sum = 0;
for (; index > 0; index &= index - 1) {
sum += f->tree[index];
}
return sum;
}
int fenwick_query(Fenwick *f, int left, int right) {
if (right < left) {
return 0;
}
return fenwick_pre(f, right) - fenwick_pre(f, left - 1);
}
int is_peak(int *nums, int i) {
return (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]);
}
void update_peak(Fenwick *f, int *nums, int i, int val) {
if (i > 0 && i < (f->size - 1)) {
if (is_peak(nums, i)) {
fenwick_update(f, i, val);
}
}
}
void count_of_peaks(int *nums, int n, int queries[][3], int query_count, int *result, int *result_count) {
Fenwick f;
fenwick_init(&f, n - 1);
for (int i = 1; i < n - 1; i++) {
update_peak(&f, nums, i, 1);
}
*result_count = 0;
for (int q = 0; q < query_count; q++) {
if (queries[q][0] == 1) {
result[(*result_count)++] = fenwick_query(&f, queries[q][1] + 1, queries[q][2] - 1);
} else {
int i = queries[q][1];
for (int j = (i > 1 ? i - 1 : 1); j <= (i < n - 2 ? i + 1 : n - 2); j++) {
update_peak(&f, nums, j, -1);
}
nums[i] = queries[q][2];
for (int j = (i > 1 ? i - 1 : 1); j <= (i < n - 2 ? i + 1 : n - 2); j++) {
update_peak(&f, nums, j, 1);
}
}
}
free(f.tree);
}
int main() {
int nums[] = {4, 1, 4, 2, 1, 5};
int n = sizeof(nums) / sizeof(nums[0]);
int queries[][3] = {{2, 2, 4}, {1, 0, 2}, {1, 0, 4}};
int query_count = sizeof(queries) / sizeof(queries[0]);
int result[query_count];
int result_count;
count_of_peaks(nums, n, queries, query_count, result, &result_count);
for (int i = 0; i < result_count; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
} 在这里插入图片描述
C++完整代码如下：
#include
#include
#include
using namespace std;
class Fenwick {
public:
vector tree;
Fenwick(int size) {
tree.resize(size + 1, 0); // 1-based index
}
void update(int index, int value) {
for (; index < tree.size(); index += index & -index) {
tree[index] += value;
}
}
int pre(int index) {
int sum = 0;
for (; index > 0; index &= index - 1) {
sum += tree[index];
}
return sum;
}
int query(int left, int right) {
if (right < left) {
return 0;
}
return pre(right) - pre(left - 1);
}
};
void update_peak(Fenwick &f, vector &nums, int i, int val) {
if (i > 0 && i < nums.size() - 1) {
if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
f.update(i, val);
}
}
}
vector count_of_peaks(vector &nums, vector> &queries) {
int n = nums.size();
Fenwick f(n - 1);
for (int i = 1; i < n - 1; ++i) {
update_peak(f, nums, i, 1);
}
vector ans;
for (const auto &q : queries) {
if (q[0] == 1) {
ans.push_back(f.query(q[1] + 1, q[2] - 1));
} else {
int i = q[1];
for (int j = max(i - 1, 1); j <= min(i + 1, n - 2); ++j) {
update_peak(f, nums, j, -1);
}
nums[i] = q[2];
for (int j = max(i - 1, 1); j <= min(i + 1, n - 2); ++j) {
update_peak(f, nums, j, 1);
}
}
}
return ans;
}
int main() {
vector nums = {4, 1, 4, 2, 1, 5};
vector> queries = {{2, 2, 4}, {1, 0, 2}, {1, 0, 4}};
vector result = count_of_peaks(nums, queries);
for (int res : result) {
cout << res << " ";
}
cout << endl;
return 0;
} 在这里插入图片描述
Python完整代码如下：
# -*-coding:utf-8-*-
class FenwickTree:
def __init__(self, size):
self.size = size
self.tree = [0] * (size + 1) # 1-based index
def update(self, index, value):
while index <= self.size:
self.tree[index] += value
index += index & -index
def prefix_sum(self, index):
total = 0
while index > 0:
total += self.tree[index]
index -= index & -index
return total
def query(self, left, right):
if right < left:
return 0
return self.prefix_sum(right) - self.prefix_sum(left - 1)
def is_peak(nums, i):
return nums[i - 1] < nums[i] > nums[i + 1]
def update_peak(fenwick_tree, nums, i, value):
if 1 <= i < len(nums) - 1:
if is_peak(nums, i):
fenwick_tree.update(i, value)
def count_of_peaks(nums, queries):
n = len(nums)
fenwick_tree = FenwickTree(n - 1)
# Initialize the Fenwick tree with the initial peak counts
for i in range(1, n - 1):
update_peak(fenwick_tree, nums, i, 1)
results = []
for query in queries:
if query[0] == 1:
results.append(fenwick_tree.query(query[1] + 1, query[2] - 1))
else:
i = query[1]
for j in range(max(i - 1, 1), min(i + 1, n - 2) + 1):
update_peak(fenwick_tree, nums, j, -1)
nums[i] = query[2]
for j in range(max(i - 1, 1), min(i + 1, n - 2) + 1):
update_peak(fenwick_tree, nums, j, 1)
return results
if __name__ == "__main__":
nums = [4, 1, 4, 2, 1, 5]
queries = [[2, 2, 4], [1, 0, 2], [1, 0, 4]]
result = count_of_peaks(nums, queries)
print(result) # Output the results在这里插入图片描述
JavaScript完整代码如下：
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0); // 使用1-based索引
}
update(index, value) {
for (let i = index; i <= this.size; i += i & -i) {
this.tree[i] += value;
}
}
prefixSum(index) {
let sum = 0;
for (let i = index; i > 0; i &= (i - 1)) {
sum += this.tree[i];
}
return sum;
}
query(left, right) {
if (right < left) {
return 0;
}
return this.prefixSum(right) - this.prefixSum(left - 1);
}
}
function isPeak(nums, i) {
return nums[i - 1] < nums[i] && nums[i] > nums[i + 1];
}
function updatePeak(fenwick, nums, i, value) {
if (i > 0 && i < nums.length - 1) {
if (isPeak(nums, i)) {
fenwick.update(i, value);
}
}
}
function countOfPeaks(nums, queries) {
const n = nums.length;
const fenwickTree = new FenwickTree(n - 1);
for (let i = 1; i < n - 1; i++) {
updatePeak(fenwickTree, nums, i, 1);
}
const results = [];
for (let q of queries) {
if (q[0] === 1) {
results.push(fenwickTree.query(q[1] + 1, q[2] - 1));
} else {
const i = q[1];
for (let j = Math.max(i - 1, 1); j <= Math.min(i + 1, n - 2); j++) {
updatePeak(fenwickTree, nums, j, -1);
}
nums[i] = q[2];
for (let j = Math.max(i - 1, 1); j <= Math.min(i + 1, n - 2); j++) {
updatePeak(fenwickTree, nums, j, 1);
}
}
}
return results;
}
// 示例
const nums = [4, 1, 4, 2, 1, 5];
const queries = [[2, 2, 4], [1, 0, 2], [1, 0, 4]];
const result = countOfPeaks(nums, queries);
console.log(result); // 输出结果在这里插入图片描述
引用链接
[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP