2024-11-28：边界元素是最大值的子数组数目。用go语言，给定一个正整数数组 nums，需要找到满足子数组中第一个和最后一个元素都是该子数组中的最大值的子数组数量。
输入：nums = [1,4,3,3,2]。
输出：6。
解释：
总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值：
子数组 [1,4,3,3,2] 的1，最大元素为 1 ，第一个和最后一个元素都是 1 。
子数组 [1,4,3,3,2] 的4，最大元素为 4 ，第一个和最后一个元素都是 4 。
子数组 [1,4,3,3,2]的第1个3 ，最大元素为 3 ，第一个和最后一个元素都是 3 。
子数组 [1,4,3,3,2] 的第2个3，最大元素为 3 ，第一个和最后一个元素都是 3 。
子数组 [1,4,3,3,2]的2 ，最大元素为 2 ，第一个和最后一个元素都是 2 。
子数组 [1,4,3,3,2] 的[3,3]，最大元素为 3 ，第一个和最后一个元素都是 3 。
所以我们返回 6 。
答案2024-11-28：
题目来自leetcode3113。
大体步骤如下：
1.初始化一个计数器 ans，开始时设为数组的长度，将 ans 的数据类型设置为 int64。
2.定义一个结构体 pair，包含两个字段 x 和 cnt，用于记录数组元素和该元素出现的次数。
3.初始化一个栈 st，其中包含一个 pair 类型的元素，该元素 x 为无穷大(math.MaxInt)，cnt 为 0，作为哨兵。
4.遍历数组 nums 中的每个元素 x：
-
如果 x 大于栈顶元素的 x，则持续弹出栈顶元素，直到栈为空或者 x 不大于栈顶元素的 x。
-
如果 x 等于栈顶元素的 x，将 ans 增加栈顶元素的 cnt，并且增加栈顶元素的 cnt 值。
-
如果 x 小于栈顶元素的 x，将一个新的 pair{x, 1} 压入栈中。
5.返回 ans。
总的时间复杂度：O(n)，其中 n 为数组 nums 的长度，因为对数组进行了一次线性遍历。
总的额外空间复杂度：O(n)，存储栈所需的空间为 O(n)。
Go完整代码如下：
package main
import (
"fmt"
"math"
)
func numberOfSubarrays(nums []int) int64 {
ans := len(nums)
type pair struct{ x, cnt int }
st := []pair{{math.MaxInt, 0}} // 无穷大哨兵
for _, x := range nums {
for x > st[len(st)-1].x {
st = st[:len(st)-1]
}
if x == st[len(st)-1].x {
ans += st[len(st)-1].cnt
st[len(st)-1].cnt++
} else {
st = append(st, pair{x, 1})
}
}
return int64(ans)
}
func main() {
nums := []int{1,4,3,3,2}
fmt.Println(numberOfSubarrays(nums))
}
Rust完整代码如下：
use std::cmp;
fn number_of_subarrays(nums: Vec<i32>) -> i64 {
let mut ans = nums.len() as i64;
let mut st: Vec<(i32, i32)> = vec![(i32::MAX, 0)]; // 使用 (值, 计数) 作为元组
for &x in &nums {
while x > st.last().unwrap().0 {
st.pop();
}
if x == st.last().unwrap().0 {
ans += st.last().unwrap().1 as i64; // 累加计数
let last = st.last_mut().unwrap();
last.1 += 1; // 计数加一
} else {
st.push((x, 1)); // 添加新值及其计数
}
}
ans
}
fn main() {
let nums = vec![1, 4, 3, 3, 2];
println!("{}", number_of_subarrays(nums));
}
