這題我寫的好坎坷
我完全忘記這些東西 我吐了
def countPartitions(self, nums: List[int], k: int) -> int:
mod = 10**9+7
# O(N^2)
# @cache
# def backtrack(idx):
# if idx>=len(nums):
# return 1
# mini = maxi = nums[idx]
# count = 0
# for i in range(idx, len(nums)):
# mini = min(mini, nums[i])
# maxi = max(maxi, nums[i])
# if (maxi-mini)>k:
# break
# count = (count+backtrack(i+1)) % mod
# return count
# find right_max_i
n = len(nums)
min_q = deque([0]) # by indx to handle duplicate number
max_q = deque([0]) # by indx to handle duplicate number
right_most_i = [n]*n
l = 0
for i in range(1,n): # [l, i]
while max_q and nums[i]>=nums[max_q[-1]]:
max_q.pop()
max_q.append(i)
while min_q and nums[i]<=nums[min_q[-1]]:
min_q.pop()
min_q.append(i)
while max_q and min_q:
cur_min = nums[min_q[0]]
cur_max = nums[max_q[0]]
if (cur_max-cur_min) > k:
right_most_i[l] = i
if max_q[0]==l:
max_q.popleft()
if min_q[0]==l:
min_q.popleft()
l += 1
else:
break
# DP
dp = [0]*(n+1)
postfix_S = [0]*(n+1)
dp[n] = 1
cur_s = 0
for i in range(n-1, -1, -1):
dp[i] = ((postfix_S[i+1]-postfix_S[right_most_i[i]]) + dp[right_
most_i[i]]) % mod
cur_s = (cur_s + dp[i]) % mod
postfix_S[i] = cur_s
return dp[0]