Medium
题目描述
给你一个由不同元素组成的整数数组 nums。
如果 nums 的子数组 nums[l...r] 满足以下条件，则称其为碗形子数组：
- 子数组长度至少为 3，即
r - l + 1 >= 3 - 两端元素的最小值严格大于中间所有元素的最大值，即
min(nums[l], nums[r]) > max(nums[l + 1], ..., nums[r - 1])
返回 nums 中碗形子数组的数量。
示例 1：
输入：nums = [2,5,3,1,4]
输出：2
解释：
碗形子数组是 [3, 1, 4] 和 [5, 3, 1, 4]。
- [3, 1, 4] 是碗形，因为 min(3, 4) = 3 > max(1) = 1
- [5, 3, 1, 4] 是碗形，因为 min(5, 4) = 4 > max(3, 1) = 3
示例 2：
输入：nums = [5,1,2,3,4]
输出：3
解释：
碗形子数组是 [5, 1, 2]、[5, 1, 2, 3] 和 [5, 1, 2, 3, 4]。
示例 3：
输入：nums = [1000000000,999999999,999999998]
输出：0
解释：
没有子数组是碗形的。
提示：
3 <= nums.length <= 10^51 <= nums[i] <= 10^9nums由不同元素组成
解题思路
这道题需要找出满足"两端最小值大于中间最大值"的子数组。关键观察是碗形条件的对称性。
核心思路：
我们可以分两种情况讨论：
- 左端点较小：
nums[l] < nums[r]且nums[l] > max(nums[l+1]...nums[r-1]) - 右端点较小：
nums[r] < nums[l]且nums[r] > max(nums[l+1]...nums[r-1])
单调栈优化：
使用单调栈预处理每个位置：
nextGreater[i]：位置 i 右侧第一个大于nums[i]的位置prevGreater[i]：位置 i 左侧第一个大于nums[i]的位置
对于情况1（左端点较小），我们枚举左端点 l，找到所有满足条件的右端点 r：
nums[l] < nums[r]（右端点更大）- 中间区域
[l+1, r-1]的所有元素都小于nums[l]
这意味着区间 [l+1, r-1] 内不能有大于等于 nums[l] 的元素。通过单调栈，我们可以快速确定有效的右端点范围。
算法步骤：
- 预处理单调栈，获取每个位置的 nextGreater 和 prevGreater
- 枚举左端点，利用单调栈信息快速计算有效右端点数量
- 处理两种情况并求和
时间复杂度 O(n)，空间复杂度 O(n)。
代码实现
class Solution {
public:
long long bowlSubarrays(vector<int>& nums) {
int n = nums.size();
vector<int> nextGreater(n, n), prevGreater(n, -1);
// 单调栈求右侧第一个更大元素
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && nums[st.top()] < nums[i]) {
nextGreater[st.top()] = i;
st.pop();
}
st.push(i);
}
// 单调栈求左侧第一个更大元素
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && nums[st.top()] < nums[i]) {
prevGreater[st.top()] = i;
st.pop();
}
st.push(i);
}
long long result = 0;
// 情况1：左端点较小
for (int l = 0; l < n - 2; l++) {
int rightBound = nextGreater[l];
for (int r = l + 2; r < rightBound && r < n; r++) {
if (nums[r] > nums[l]) {
result++;
}
}
}
// 情况2：右端点较小
for (int r = 2; r < n; r++) {
int leftBound = prevGreater[r];
for (int l = max(0, leftBound + 1); l <= r - 2; l++) {
if (nums[l] > nums[r]) {
result++;
}
}
}
return result;
}
};
class Solution:
def bowlSubarrays(self, nums: List[int]) -> int:
n = len(nums)
next_greater = [n] * n
prev_greater = [-1] * n
# 单调栈求右侧第一个更大元素
stack = []
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
next_greater[stack.pop()] = i
stack.append(i)
# 单调栈求左侧第一个更大元素
stack = []
for i in range(n - 1, -1, -1):
while stack and nums[stack[-1]] < nums[i]:
prev_greater[stack.pop()] = i
stack.append(i)
result = 0
# 情况1：左端点较小
for l in range(n - 2):
right_bound = next_greater[l]
for r in range(l + 2, min(right_bound, n)):
if nums[r] > nums[l]:
result += 1
# 情况2：右端点较小
for r in range(2, n):
left_bound = prev_greater[r]
for l in range(max(0, left_bound + 1), r - 1):
if nums[l] > nums[r]:
result += 1
return result
public class Solution {
public long BowlSubarrays(int[] nums) {
int n = nums.Length;
int[] nextGreater = new int[n];
int[] prevGreater = new int[n];
Array.Fill(nextGreater, n);
Array.Fill(prevGreater, -1);
// 单调栈求右侧第一个更大元素
Stack<int> stack = new Stack<int>();
for (int i = 0; i < n; i++) {
while (stack.Count > 0 && nums[stack.Peek()] < nums[i]) {
nextGreater[stack.Pop()] = i;
}
stack.Push(i);
}
// 单调栈求左侧第一个更大元素
stack.Clear();
for (int i = n - 1; i >= 0; i--) {
while (stack.Count > 0 && nums[stack.Peek()] < nums[i]) {
prevGreater[stack.Pop()] = i;
}
stack.Push(i);
}
long result = 0;
// 情况1：左端点较小
for (int l = 0; l < n - 2; l++) {
int rightBound = nextGreater[l];
for (int r = l + 2; r < rightBound && r < n; r++) {
if (nums[r] > nums[l]) {
result++;
}
}
}
// 情况2：右端点较小
for (int r = 2; r < n; r++) {
int leftBound = prevGreater[r];
for (int l = Math.Max(0, leftBound + 1); l <= r - 2; l++) {
if (nums[l] > nums[r]) {
result++;
}
}
}
return result;
}
}
var bowlSubarrays = function(nums) {
const n = nums.length;
const nextGreater = new Array(n).fill(n);
const prevGreater = new Array(n).fill(-1);
// 单调栈求右侧第一个更大元素
let stack = [];
for (let i = 0; i < n; i++) {
while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
nextGreater[stack.pop()] = i;
}
stack.push(i);
}
// 单调栈求左侧第一个更大元素
stack = [];
for (let i = n - 1; i >= 0; i--) {
while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
prevGreater[stack.pop()] = i;
}
stack.push(i);
}
let result = 0;
// 情况1：左端点较小
for (let l = 0; l < n - 2; l++) {
const rightBound = nextGreater[l];
for (let r = l + 2; r < rightBound && r < n; r++) {
if (nums[r] > nums[l]) {
result++;
}
}
}
// 情况2：右端点较小
for (let r = 2; r < n; r++) {
const leftBound = prevGreater[r];
for (let l = Math.max(0, leftBound + 1); l <= r - 2; l++) {
if (nums[l] > nums[r]) {
result++;
}
}
}
return result;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(n) |
注：虽然使用了单调栈优化预处理到O(n)，但在枚举有效端点时仍需O(n²)的时间复杂度。空间复杂度为O(n)用于存储单调栈结果。