Question

2393. Count Strictly Increasing Subarrays

中文文档

Description

You are given an array nums consisting of positive integers.

Return _the number of subarrays of _nums_ that are in strictly increasing order._

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1,3,5,4,4,6]
Output: 10
Explanation: The strictly increasing subarrays are the following:
- Subarrays of length 1: [1], [3], [5], [4], [4], [6].
- Subarrays of length 2: [1,3], [3,5], [4,6].
- Subarrays of length 3: [1,3,5].
The total number of subarrays is 6 + 3 + 1 = 10.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 15
Explanation: Every subarray is strictly increasing. There are 15 possible subarrays that we can take.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106

Solutions

Solution 1

class Solution:
  def countSubarrays(self, nums: List[int]) -> int:
    ans = i = 0
    while i < len(nums):
      j = i + 1
      while j < len(nums) and nums[j] > nums[j - 1]:
        j += 1
      cnt = j - i
      ans += (1 + cnt) * cnt // 2
      i = j
    return ans

class Solution {
  public long countSubarrays(int[] nums) {
    long ans = 0;
    int i = 0, n = nums.length;
    while (i < n) {
      int j = i + 1;
      while (j < n && nums[j] > nums[j - 1]) {
        ++j;
      }
      long cnt = j - i;
      ans += (1 + cnt) * cnt / 2;
      i = j;
    }
    return ans;
  }
}

class Solution {
public:
  long long countSubarrays(vector<int>& nums) {
    long long ans = 0;
    int i = 0, n = nums.size();
    while (i < n) {
      int j = i + 1;
      while (j < n && nums[j] > nums[j - 1]) {
        ++j;
      }
      int cnt = j - i;
      ans += 1ll * (1 + cnt) * cnt / 2;
      i = j;
    }
    return ans;
  }
};

func countSubarrays(nums []int) int64 {
  ans := 0
  i, n := 0, len(nums)
  for i < n {
    j := i + 1
    for j < n && nums[j] > nums[j-1] {
      j++
    }
    cnt := j - i
    ans += (1 + cnt) * cnt / 2
    i = j
  }
  return int64(ans)
}

function countSubarrays(nums: number[]): number {
  let ans = 0;
  let i = 0;
  const n = nums.length;
  while (i < n) {
    let j = i + 1;
    while (j < n && nums[j] > nums[j - 1]) {
      ++j;
    }
    const cnt = j - i;
    ans += ((1 + cnt) * cnt) / 2;
    i = j;
  }
  return ans;
}

Solution 2

class Solution:
  def countSubarrays(self, nums: List[int]) -> int:
    ans = pre = cnt = 0
    for x in nums:
      if pre < x:
        cnt += 1
      else:
        cnt = 1
      pre = x
      ans += cnt
    return ans

class Solution {
  public long countSubarrays(int[] nums) {
    long ans = 0;
    int pre = 0, cnt = 0;
    for (int x : nums) {
      if (pre < x) {
        ++cnt;
      } else {
        cnt = 1;
      }
      pre = x;
      ans += cnt;
    }
    return ans;
  }
}

class Solution {
public:
  long long countSubarrays(vector<int>& nums) {
    long long ans = 0;
    int pre = 0, cnt = 0;
    for (int x : nums) {
      if (pre < x) {
        ++cnt;
      } else {
        cnt = 1;
      }
      ans += cnt;
      pre = x;
    }
    return ans;
  }
};

func countSubarrays(nums []int) (ans int64) {
  pre, cnt := 0, 0
  for _, x := range nums {
    if pre < x {
      cnt++
    } else {
      cnt = 1
    }
    ans += int64(cnt)
    pre = x
  }
  return
}

function countSubarrays(nums: number[]): number {
  let ans = 0;
  let pre = 0;
  let cnt = 0;
  for (const x of nums) {
    if (pre < x) {
      ++cnt;
    } else {
      cnt = 1;
    }
    ans += cnt;
    pre = x;
  }
  return ans;
}