LC.P795[区间子数组个数]

方法一：单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {

    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int n = nums.length;
        int[] l = new int[n], r = new int[n];
        Arrays.fill(l, -1);
        Arrays.fill(r, n);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            // 求nums[i]的左侧第一个大于该元素的下标l[i]
            int num = nums[i];
            while (!stack.isEmpty() && nums[stack.peek()] <= num) stack.pop();
            if (!stack.isEmpty()) l[i] = stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            // 求nums[i]的右侧第一个大于等于该元素的下标r[i]
            int num = nums[i];
            while (!stack.isEmpty() && nums[stack.peek()] < num) stack.pop();
            if (!stack.isEmpty()) r[i] = stack.peek();
            stack.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;
    }

}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：区间计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {

    // 对于区间[left, right]的问题，将其转换为[0, right]然后减去[0, left - 1]的问题
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }

    private int count(int[] nums, int x) {
        int cnt = 0, len = 0;
        for (int num : nums) {
            len = num > x ? 0 : len + 1;
            cnt += len;
        }
        return cnt;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

方法三：一次遍历

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int n = nums.length, ans = 0, i0 = -1, i1 = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > right) i0 = i;
            if (nums[i] >= left) i1 = i;
            ans += i1 - i0;
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$