README_EN.md

1708. Largest Subarray Length K

中文文档

Description

An array A is larger than some array B if for the first index i where A[i] != B[i], A[i] > B[i].

For example, consider 0-indexing:

• [1,3,2,4] > [1,2,2,4], since at index 1, 3 > 2.
• [1,4,4,4] < [2,1,1,1], since at index 0, 1 < 2.

A subarray is a contiguous subsequence of the array.

Given an integer array nums of distinct integers, return the largest subarray of nums of length k.

 

Example 1:

Input: nums = [1,4,5,2,3], k = 3
Output: [5,2,3]
Explanation: The subarrays of size 3 are: [1,4,5], [4,5,2], and [5,2,3].
Of these, [5,2,3] is the largest.

Example 2:

Input: nums = [1,4,5,2,3], k = 4
Output: [4,5,2,3]
Explanation: The subarrays of size 4 are: [1,4,5,2], and [4,5,2,3].
Of these, [4,5,2,3] is the largest.

Example 3:

Input: nums = [1,4,5,2,3], k = 1
Output: [5]

 

Constraints:

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 109
• All the integers of nums are unique.

 

Follow up: What if the integers in nums are not distinct?

Solutions

Python3

class Solution:
    def largestSubarray(self, nums: List[int], k: int) -> List[int]:
        mx = max(nums[: len(nums) - k + 1])
        i = nums.index(mx)
        return nums[i : i + k]

Java

class Solution {
    public int[] largestSubarray(int[] nums, int k) {
        int i = 0, mx = 0;
        for (int j = 0; j < nums.length - k + 1; ++j) {
            if (mx < nums[j]) {
                mx = nums[j];
                i = j;
            }
        }
        int[] ans = new int[k];
        for (int j = 0; j < k; ++j) {
            ans[j] = nums[i + j];
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> largestSubarray(vector<int>& nums, int k) {
        auto pos = max_element(nums.begin(), nums.begin() + nums.size() - k + 1);
        return {pos, pos + k};
    }
};

Rust

impl Solution {
    #[allow(dead_code)]
    pub fn largest_subarray(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut ret_vec = vec![i32::MIN];
        let n = nums.len();

        if n == k as usize {
            return nums;
        }

        for i in 0..=n - k as usize {
            if nums[i] > ret_vec[0] {
                ret_vec = nums[i..i + k as usize].to_vec();
            }
        }

        ret_vec
    }
}

Go

func largestSubarray(nums []int, k int) []int {
	i, mx := 0, 0
	for j := 0; j < len(nums)-k+1; j++ {
		if mx < nums[j] {
			mx = nums[j]
			i = j
		}
	}
	return nums[i : i+k]
}

...