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 mainimport ( "fmt")type fenwick []intfunc (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<i32>,}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<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> { 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 <stdio.h>#include <stdlib.h>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 <iostream>#include <vector>#include <algorithm>using namespace std;class Fenwick {public: vector<int> 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<int> &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<int> count_of_peaks(vector<int> &nums, vector<vector<int>> &queries) { int n = nums.size(); Fenwick f(n - 1); for (int i = 1; i < n - 1; ++i) { update_peak(f, nums, i, 1); } vector<int> 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<int> nums = {4, 1, 4, 2, 1, 5}; vector<vector<int>> queries = {{2, 2, 4}, {1, 0, 2}, {1, 0, 4}}; vector<int> 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 resultsif __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
