难度: 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 个元素时，最后一个考虑的子数组正好是从这个元素开始到数组末尾的子数组。因此，这个终止条件是合理的，确保了包括数组末尾的所有子数组都被考虑。