• Leetcode 3152. Special Array II
  • 1. 解題思路
  • 2. 代碼實(shí)現(xiàn)

• 題目鏈接：3152. Special Array II

1. 解題思路

這一題的話思路上就是分堆，使用貪婪算法找到每一個(gè)元素所在的最長(zhǎng)special子序列，然后判斷query的首尾元素是不是屬于同一個(gè)special子序列即可。

具體實(shí)現(xiàn)上的話可以使用DSU，不過也可以簡(jiǎn)化一下，直接將每一個(gè)special子序列用其首元素表示即可。

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(xiàn)如下：

class Solution:def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:n = len(nums)group = [i for i in range(n)]for i in range(n-1):if nums[i] % 2 != nums[i+1] % 2:group[i+1] = group[i]return [group[i] == group[j] for i, j in queries]

提交代碼評(píng)測(cè)得到：耗時(shí)915ms，占用內(nèi)存56.4MB。