NeetCode #696LC-2393Medium1-D Dynamic Programming
← Back to All Problems#696 · #2393 · Count Strictly Increasing Subarrays(统计严格递增子数组的数目)
📌 Problem Statement & Constraints
Given an integer array
nums, return the number of contiguous subarrays that are strictly increasing. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- Every contiguous subarray of a strictly increasing run is itself strictly increasing.
- Let
curbe the length of the strictly increasing run ending at the current index. - If
nums[i] > nums[i-1], extend the run withcur += 1; otherwise restart withcur = 1. - Each index contributes exactly
curnew increasing subarrays, namely all suffixes of the current run.
💻 Benchmark Python3 Implementation
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
total = 0
cur = 0 # length of the increasing run ending here
for i, x in enumerate(nums):
if i > 0 and x > nums[i - 1]:
cur += 1
else:
cur = 1
total += cur # every suffix of the run is valid
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a single left-to-right pass.
💾 Space Complexity
O(1): two counters.
⚠️ Interview Pitfalls & Follow-ups
- Using
>=instead of>: the subarrays must be strictly increasing, so equal neighbours break the run. - Counting only maximal runs: every sub-run counts, which is why
curis added at each index. - Resetting
curto 0: the current element alone is always a length-1 increasing subarray, so the reset value is 1. - Enumerating subarrays directly: that is O(n^2) and too slow for
n = 10^5.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.