返回介绍

solution / 2300-2399 / 2393.Count Strictly Increasing Subarrays / README

发布于 2024-06-17 01:03:06 字数 4923 浏览 0 评论 0 收藏 0

2393. 严格递增的子数组个数

English Version

题目描述

给定一个由 正整数 组成的数组 nums

返回 _严格递增 顺序的 _nums子数组 的数目。_

子数组 是数组的一部分,且是 连续 的。

 

示例 1:

输入: nums = [1,3,5,4,4,6]
输出: 10
解释: 严格递增的子数组如下:
- 长度为 1 的子数组: [1], [3], [5], [4], [4], [6]。
- 长度为 2 的子数组: [1,3], [3,5], [4,6]。
- 长度为 3 的子数组: [1,3,5]。
子数组的总数是 6 + 3 + 1 = 10。

示例 2:

输入: nums = [1,2,3,4,5]
输出: 15
解释: 每个子数组都严格递增。我们可以取 15 个子数组。

 

提示:

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

解法

方法一:双指针

利用双指针,找到每一段连续递增子数组的长度,我们记为 cnt,每次将 $(1+cnt)\times cnt / 2$ 累加到答案中。

时间复杂度 $O(n)$,空间复杂度 $O(1)$,其中 $n$ 是数组的长度。

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;
}

方法二:枚举

我们可以枚举数组中的每一个元素,找到以该元素为结尾的严格递增子数组的个数,然后将这些个数累加到答案中。

时间复杂度 $O(n)$,空间复杂度 $O(1)$,其中 $n$ 是数组的长度。

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;
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文