2972.incremovable_subarray_count

. - 力扣（LeetCode）

开始思路有问题，简单看了提示才有思路，思路大概是先不考虑后缀的保留，只考虑保留前缀有多少个移除递增子数组，然后再考虑后缀的保留。

from typing import List
 
 
class Solution:
	def incremovableSubarrayCount(self, nums: List[int]) -> int:
		n = len(nums)
		# 循环数组，记录数组中大于等于后面一位元素，以及小于等于前一位元素的索引
		more_than_number_index: List[int] = []
		for i in range(n - 1):
			if nums[i] >= nums[i + 1]:
				more_than_number_index.append(i)
			if nums[i + 1] <= nums[i]:
				more_than_number_index.append(i + 1)
 
		if not more_than_number_index:
			return n * (n + 1) // 2
 
		# 找到数组中最小的索引
		min_index = more_than_number_index[0]
 
		# 找到数组中最大的索引
		max_index = more_than_number_index[-1]
		# 只考虑前缀为严格递增数组的组合排列总数
		sums = min_index + 1 + 1
 
		# 记录每次循环结束时前缀的索引位置
		count = 0
		# 循环可能保留的后置数组的严格递增数组
		for i in range(max_index, n):
			# 直接从索引位置开始循环即可，索引前面的不可能大于等于后缀向后一位的元素
			for j in range(count, i + 1):
				# 如果前缀的索引为j元素大于等于后缀索引为i的元素，保留当前i位后缀的可能性有j+1次，结束i位后缀的循环
				if nums[j] >= nums[i]:
					sums += j + 1
					count = j
					break
 
				# 如果前缀的索引为j元素大于等于前缀的索引为j+1的元素，保留当前i位后缀的可能性有j+2次，结束i位后缀的循环
				elif nums[j] >= nums[j + 1]:
					sums += j + 2
					count = j
					break
 
		return sums
 
	def incremovableSubarrayCount(self, nums: List[int]) -> int:
		n = len(nums)
		# 循环数组，记录数组中大于等于后面一位元素，以及小于等于前一位元素的索引
		more_than_number_index: List[int] = []
		for i in range(n - 1):
			if nums[i] >= nums[i + 1]:
				more_than_number_index.append(i)
			if nums[i + 1] <= nums[i]:
				more_than_number_index.append(i + 1)
 
		if not more_than_number_index:
			return n * (n + 1) // 2
 
		# 找到数组中最小的索引
		min_index = more_than_number_index[0]
 
		# 找到数组中最大的索引
		max_index = more_than_number_index[-1]
		# 只考虑前缀为严格递增数组的组合排列总数
		sums = min_index + 1 + 1
 
		# 记录每次循环结束时前缀的索引位置
		count = 0
		# 循环可能保留的后置数组的严格递增数组
		for i in range(max_index, n):
			# 直接从索引位置开始循环即可，索引前面的不可能大于等于后缀向后一位的元素
			for j in range(count, i + 1):
				# 如果前缀的索引为j元素大于等于后缀索引为i的元素，保留当前i位后缀的可能性有j+1次，结束i位后缀的循环
				if nums[j] >= nums[i]:
					sums += j + 1
					count = j
					break
 
				# 如果前缀的索引为j元素大于等于前缀的索引为j+1的元素，保留当前i位后缀的可能性有j+2次，结束i位后缀的循环
				elif nums[j] >= nums[j + 1]:
					sums += j + 2
					count = j
					break
 
		return sums
 
# 以上是我的解题通过的结果，结果显示时间与空间复杂度都是垫底的。
 
 
# 参考别人的解法，进行的改造，效率也差不多！！
	def incremovableSubarrayCountMyExpend(self, nums: List[int]) -> int:
		n = len(nums)
		# 循环数组，记录数组中大于等于后面一位元素，以及小于等于前一位元素的索引
		more_than_number_index: List[int] = []
		for i in range(n - 1):
			if nums[i] >= nums[i + 1]:
				more_than_number_index.append(i)
			if nums[i + 1] <= nums[i]:
				more_than_number_index.append(i + 1)
 
		if not more_than_number_index:
			return n * (n + 1) // 2
 
		# 找到数组中最小的索引
		min_index = more_than_number_index[0]
 
		# 找到数组中最大的索引
		max_index = more_than_number_index[-1]
		# 只考虑前缀为严格递增数组的组合排列总数
		sums = min_index + 1 + 1
 
		i = n - 1
		j = min_index
 
		# 循环可能保留的后置数组的严格递增数组，当后缀指针i的元素小于i+1的元素可保留该后缀的统计
		while i == n - 1 or nums[i] < nums[i + 1]:
			while j >= 0 and nums[j] >= nums[i]:
				j -= 1
			sums += j + 2
			i -= 1
 
		return sums
 
 
# main
s = Solution()
print(s.incremovableSubarrayCountMyExpend([8, 7, 6, 6]))
print(s.incremovableSubarrayCount([8, 7, 6, 6]))