【单调栈 +前缀和】AcWing 4738. 快乐子数组

**快乐子数组**

**题目描述**

给定一个整数数组 `arr` 和一个整数 `k`,要求找出所有满足以下条件的子数组：

* 子数组中每个元素都是正整数。
* 子数组中的每个元素都大于或等于其索引（从0 开始）。
* 子数组中的每个元素都小于或等于其索引加上 `k`。

**示例**

输入：`arr = [1,2,3,4,5]`, `k =2`

输出：`[[1],[2],[3]]`

**思路**

我们可以使用单调栈和前缀和来解决这个问题。首先，我们计算出每个元素的前缀和，然后使用单调栈来维护一个子数组的集合。

**代码**

class Solution:
 def getHappySubarrays(self, arr: List[int], k: int) -> List[List[int]]:
 n = len(arr)
 prefix_sum = [0] * (n +1)
 for i in range(n):
 prefix_sum[i +1] = prefix_sum[i] + arr[i]

 stack = []
 res = []

 for i in range(n):
 while stack and stack[-1][0] > i:
 top = stack.pop()
 if top[1] <= i + k:
 res.append(top[1:])
 stack.append((i, [arr[i]]))

 return res