Leetcode 3101. Count Alternating Subarrays
最编程
2024-04-01 15:52:06
...
-
Leetcode 3101. Count Alternating Subarrays
- 1. 解题思路
- 2. 代码实现
- 题目链接:3101. Count Alternating Subarrays
1. 解题思路
这一题我们只需要用贪婪算法对原数组进行切分,使得每一段都是最大的交错子序列,然后,我们要获得所有交错子序列的个数,就只需要在每一段上进行 C n + 1 2 C_{n+1}^2 Cn+12的首尾选择即可。
2. 代码实现
给出python代码实现如下:
class Solution:
def countAlternatingSubarrays(self, nums: List[int]) -> int:
i, j, n = 0, 0, len(nums)
ans = 0
while i < n:
pre = 1-nums[i]
while j < n and nums[j] == 1-pre:
j += 1
pre = 1-pre
k = j-i
ans += k * (k+1) // 2
i = j
return ans
提交代码评测得到:耗时810ms,占用内存20MB。