3676. Count Bowl Subarrays

You are given an integer array nums with distinct elements.

A subarray nums[l...r] of nums is called a bowl if:

• The subarray has length at least 3. That is, r - l + 1 >= 3.
• The minimum of its two ends is strictly greater than the maximum of all elements in between. That is, min(nums[l], nums[r]) > max(nums[l + 1], ..., nums[r - 1]).

Return the number of bowl subarrays in nums.

class Solution {
public:
    long long bowlSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> gr(n, -1), le(n, -1), st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() and nums[st.back()] < nums[i]) {
                gr[st.back()] = i;
                st.pop_back();
            }
            st.push_back(i);
        }
        st = {};
        for (int i = 0; i < n; ++i) {
            while (!st.empty() and nums[st.back()] < nums[i]) st.pop_back();
            if (!st.empty()) le[i] = st.back();
            st.push_back(i);
        }
        long long res = 0;
        for (int i = 0; i < n; ++i) {
            if (gr[i] != -1 and gr[i] - i >= 2) ++res;
            if (le[i] != -1 and i - le[i] >= 2) ++res;
        }
        return res;
    }
};