题目截图

题目分析

• 无脑单调栈左右找更大
• 注意一边不取等，一边取等，避免重复
• 找到包含当前元素为最大值的区间个数，左 * 右即可

python

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left_: int, right_: int) -> int:
       # 单调栈
        n = len(nums)
        # 左边比自己大的最近的位置
        left, st = [-1] * n, []
        for i, v in enumerate(nums):
            while st and nums[st[-1]] < v: st.pop()
            if st: left[i] = st[-1]
            st.append(i)
        
        # 右边比自己大于等于的最近的位置
        right, st = [n] * n, []
        for i in range(n - 1, -1, -1):
            while st and nums[st[-1]] <= nums[i]: st.pop()
            if st: right[i] = st[-1]
            st.append(i)
        
        # 当前元素作为最大值的区域
        #print(left)
        #print(right)
        ans = 0
        for i in range(n):
            l, r = i - left[i], right[i] - i
            if left_ <= nums[i] <= right_:
                #print(nums[i], l, r)
                ans += l * r
        return ans

java

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        // java单调栈
        int n = nums.length;
        int[] L = new int[n], R = new int[n];
        Arrays.fill(L, -1);
        Arrays.fill(R, n);
        Deque<Integer> st = new ArrayDeque<>();
        // 左边比自己大的最近的位置
        for (int i = 0; i < n; ++i) {
            while (!st.isEmpty() && nums[st.peek()] < nums[i]) st.pop();
            if (!st.isEmpty()) L[i] = st.peek();
            st.push(i);
        }
        // 右边比自己大于等于的最近的位置
        st.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.isEmpty() && nums[st.peek()] <= nums[i]) st.pop();
            if (!st.isEmpty()) R[i] = st.peek();
            st.push(i);
        }
        // 当前元素作为最大值的区域
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left <= nums[i] && nums[i] <= right) {
                ans += (i - L[i]) * (R[i] - i);
            }
        }
        return ans;

    }
}

• int[] l = new int[n];
• Deque st = new ArrayDeque<>();
• st.peak()
• st.pop()
• st.push(i)

总结

• 单调栈无脑
• 继续熟悉java