Question

795. Number of Subarrays with Bounded Maximum

中文文档

Description

Given an integer array nums and two integers left and right, return _the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range _[left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

 

Example 1:

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Example 2:

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= left <= right <= 109

Solutions

Solution 1

class Solution:
  def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
    def f(x):
      cnt = t = 0
      for v in nums:
        t = 0 if v > x else t + 1
        cnt += t
      return cnt

    return f(right) - f(left - 1)

class Solution {
  public int numSubarrayBoundedMax(int[] nums, int left, int right) {
    return f(nums, right) - f(nums, left - 1);
  }

  private int f(int[] nums, int x) {
    int cnt = 0, t = 0;
    for (int v : nums) {
      t = v > x ? 0 : t + 1;
      cnt += t;
    }
    return cnt;
  }
}

class Solution {
public:
  int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
    auto f = [&](int x) {
      int cnt = 0, t = 0;
      for (int& v : nums) {
        t = v > x ? 0 : t + 1;
        cnt += t;
      }
      return cnt;
    };
    return f(right) - f(left - 1);
  }
};

func numSubarrayBoundedMax(nums []int, left int, right int) int {
  f := func(x int) (cnt int) {
    t := 0
    for _, v := range nums {
      t++
      if v > x {
        t = 0
      }
      cnt += t
    }
    return
  }
  return f(right) - f(left-1)
}

Solution 2

class Solution:
  def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
    n = len(nums)
    l, r = [-1] * n, [n] * n
    stk = []
    for i, v in enumerate(nums):
      while stk and nums[stk[-1]] <= v:
        stk.pop()
      if stk:
        l[i] = stk[-1]
      stk.append(i)
    stk = []
    for i in range(n - 1, -1, -1):
      while stk and nums[stk[-1]] < nums[i]:
        stk.pop()
      if stk:
        r[i] = stk[-1]
      stk.append(i)
    return sum(
      (i - l[i]) * (r[i] - i) for i, v in enumerate(nums) if left <= v <= right
    )

class Solution {
  public int numSubarrayBoundedMax(int[] nums, int left, int right) {
    int n = nums.length;
    int[] l = new int[n];
    int[] r = new int[n];
    Arrays.fill(l, -1);
    Arrays.fill(r, n);
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      int v = nums[i];
      while (!stk.isEmpty() && nums[stk.peek()] <= v) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        l[i] = stk.peek();
      }
      stk.push(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
      int v = nums[i];
      while (!stk.isEmpty() && nums[stk.peek()] < v) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        r[i] = stk.peek();
      }
      stk.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;
  }
}

class Solution {
public:
  int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
    int n = nums.size();
    vector<int> l(n, -1);
    vector<int> r(n, n);
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
      int v = nums[i];
      while (!stk.empty() && nums[stk.top()] <= v) stk.pop();
      if (!stk.empty()) l[i] = stk.top();
      stk.push(i);
    }
    stk = stack<int>();
    for (int i = n - 1; ~i; --i) {
      int v = nums[i];
      while (!stk.empty() && nums[stk.top()] < v) stk.pop();
      if (!stk.empty()) r[i] = stk.top();
      stk.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;
  }
};

func numSubarrayBoundedMax(nums []int, left int, right int) (ans int) {
  n := len(nums)
  l := make([]int, n)
  r := make([]int, n)
  for i := range l {
    l[i], r[i] = -1, n
  }
  stk := []int{}
  for i, v := range nums {
    for len(stk) > 0 && nums[stk[len(stk)-1]] <= v {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      l[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  stk = []int{}
  for i := n - 1; i >= 0; i-- {
    v := nums[i]
    for len(stk) > 0 && nums[stk[len(stk)-1]] < v {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      r[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  for i, v := range nums {
    if left <= v && v <= right {
      ans += (i - l[i]) * (r[i] - i)
    }
  }
  return
}