难度: Easy
Submission
运行时间: 50 ms
内存: 28.1 MB
class Solution: def largestSubarray(self, nums: List[int], k: int) -> List[int]: maxIdx = 0 for i in range(1, len(nums) - k + 1): if nums[i] > nums[maxIdx]: maxIdx = i return nums[maxIdx: maxIdx + k]
Explain
该题解的核心思路是通过一次遍历找到长度为 K 的最大子数组的起始索引。首先初始化最大子数组的起始索引 maxIdx 为 0。然后从索引 1 开始遍历到 len(nums) - k,比较当前元素 nums[i] 和 nums[maxIdx],如果当前元素更大,则更新 maxIdx 为当前索引 i。这样保证了 maxIdx 指向的是在数组中找到的最大的首元素的索引,对应的子数组就是全局最大的长度为 K 的子数组。遍历结束后,返回从 maxIdx 到 maxIdx + k 的子数组。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution: def largestSubarray(self, nums: List[int], k: int) -> List[int]: maxIdx = 0 # 初始化最大子数组的起始索引为 0 for i in range(1, len(nums) - k + 1): # 从 1 开始到 n-k+1 遍历数组 if nums[i] > nums[maxIdx]: # 比较当前元素与目前找到的最大元素 maxIdx = i # 更新最大子数组的起始索引 return nums[maxIdx: maxIdx + k] # 返回最大子数组
Explore
该算法的核心思路是通过比较子数组的首元素来决定最大子数组,这并不是基于子数组的总和或其他统计信息,而仅仅是首元素的大小。因此,这种方法并不能保证找到的子数组在总和或其他统计意义上最大,只能保证在所有长度为 K 的子数组中,选出了首元素最大的一个。
该算法确实只通过首元素的大小来确定子数组的最大值,这种方法假设首元素最大的子数组也是最大的子数组,这是一个局限性。实际上,如果考虑子数组的总和或其他综合因素作为最大的判断标准,仅依靠首元素大小是不足够的,可能需要额外的逻辑来计算和比较每个子数组的总和或其他标准。
当数组长度等于 K 时,整个数组就是唯一的一个子数组,因此不需要任何遍历或比较,直接返回整个数组即可。如果数组长度接近 K,例如长度为 K+1,该算法仍会正常工作,比较可能的两个子数组的首元素,找出首元素较大的子数组。此时,遍历的次数减少,但没有特殊的优化措施。
这个终止条件确保了算法考虑了所有可能的子数组。由于子数组的长度固定为 K,当遍历到数组的倒数第 K 个元素时,最后一个考虑的子数组正好是从这个元素开始到数组末尾的子数组。因此,这个终止条件是合理的,确保了包括数组末尾的所有子数组都被考虑。