题目描述

给你一个 正 整数数组 nums。

请你求出 nums 中有多少个子数组，满足子数组中 第一个 和 最后一个 元素都是这个子数组中的 最大 值。

样例

输入：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 。

输入：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。

输入：nums = [1]

输出：1

解释：

nums 中只有一个子数组 [1]，最大元素为 1，第一个和最后一个元素都是 1。

所以我们返回 1。

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

算法

(单调栈) $O(n)$

1. 维护一个严格单调递减的栈，栈中记录元素的值和这个值的出现次数。
2. 遍历数组，遍历过程中，如果当前元素的值大于单调栈的栈顶元素，则栈顶元素出栈，直到栈顶元素的值大于或等于当前元素的值。
3. 如果当前栈顶元素的值等于当前元素的值，则说明当前元素和栈顶元素的每一次「出现」，都可以构成一个以当前元素结尾的合法的子数组（包括当前元素自己），且最终栈顶元素的出现次数加一。
4. 否则，当前元素入栈，出现次数为 1，答案自增 1（当前元素作为子数组）。

时间复杂度

• 每个元素进栈一次，出栈一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储栈。

C++ 代码

#define LL long long

class Solution {
public:
    LL numberOfSubarrays(vector<int>& nums) {
        const int n = nums.size();

        stack<pair<int, int>> st;
        LL ans = 0;

        for (int i = 0; i < n; i++) {
            while (!st.empty() && st.top().first < nums[i])
                st.pop();

            if (!st.empty() && st.top().first == nums[i]) {
                ++st.top().second;
                ans += st.top().second;
            } else {
                ++ans;
                st.emplace(nums[i], 1);
            }
        }

        return ans;
    }
};