class Solution {
public:
long long numberOfSubarrays(vector<int>& nums) {
}
};
100273. 边界元素是最大值的子数组数目
给你一个 正 整数数组 nums 。
请你求出 nums 中有多少个子数组，满足子数组中 第一个 和 最后一个 元素都是这个子数组中的 最大 值。
示例 1：
输入：nums = [1,4,3,3,2]
输出：6
解释：
总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值：
[1,4,3,3,2] ，最大元素为 1 ，第一个和最后一个元素都是 1 。[1,4,3,3,2] ，最大元素为 4 ，第一个和最后一个元素都是 4 。[1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。[1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。[1,4,3,3,2] ，最大元素为 2 ，第一个和最后一个元素都是 2 。[1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。所以我们返回 6 。
示例 2：
输入：nums = [3,3,3]
输出：6
解释：
总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值：
[3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。[3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。[3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。[3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。[3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。[3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。所以我们返回 6 。
示例 3：
输入：nums = [1]
输出：1
解释：
nums 中只有一个子数组 [1] ，最大元素为 1 ，第一个和最后一个元素都是 1 。
所以我们返回 1 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 101 ms, 内存消耗: 9.7 MB, 提交时间: 2024-04-15 14:27:39
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)
}
cpp 解法, 执行用时: 135 ms, 内存消耗: 108.1 MB, 提交时间: 2024-04-15 14:27:23
class Solution {
public:
long long numberOfSubarrays(vector<int>& nums) {
long long ans = nums.size();
stack<pair<int, int>> st;
st.emplace(INT_MAX, 0); // 无穷大哨兵
for (int x : nums) {
while (x > st.top().first) {
st.pop();
}
if (x == st.top().first) {
ans += st.top().second++;
} else {
st.emplace(x, 1);
}
}
return ans;
}
};
java 解法, 执行用时: 11 ms, 内存消耗: 59.1 MB, 提交时间: 2024-04-15 14:27:11
class Solution {
public long numberOfSubarrays(int[] nums) {
long ans = nums.length;
Deque<int[]> st = new ArrayDeque<>();
st.push(new int[]{Integer.MAX_VALUE, 0}); // 无穷大哨兵
for (int x : nums) {
while (x > st.peek()[0]) {
st.pop();
}
if (x == st.peek()[0]) {
ans += st.peek()[1]++;
} else {
st.push(new int[]{x, 1});
}
}
return ans;
}
}
python3 解法, 执行用时: 174 ms, 内存消耗: 33.9 MB, 提交时间: 2024-04-15 14:26:59
# 单调栈
class Solution:
def numberOfSubarrays(self, nums: List[int]) -> int:
ans = len(nums)
st = [[inf, 0]] # 无穷大哨兵
for x in nums:
while x > st[-1][0]:
st.pop()
if x == st[-1][0]:
ans += st[-1][1]
st[-1][1] += 1
else:
st.append([x, 1])
return ans