跳转至

1708. 长度为 K 的最大子数组 🔒

题目描述

在数组 A 和数组 B 中，对于第一个满足 A[i] != B[i] 的索引 i ，当 A[i] > B[i] 时，数组 A 大于数组 B。

例如，对于索引从 0 开始的数组：

  • [1,3,2,4] > [1,2,2,4] ，因为在索引 1 上， 3 > 2。
  • [1,4,4,4] < [2,1,1,1] ，因为在索引 0 上， 1 < 2。

一个数组的子数组是原数组上的一个连续子序列。

给定一个包含不同整数的整数类型数组 nums ，返回 nums 中长度为 k 的最大子数组。

 

示例 1:

输入: nums = [1,4,5,2,3], k = 3
输出: [5,2,3]
解释: 长度为 3 的子数组有： [1,4,5]、 [4,5,2] 和 [5,2,3]。
在这些数组中， [5,2,3] 是最大的。

示例 2:

输入: nums = [1,4,5,2,3], k = 4
输出: [4,5,2,3]
解释: 长度为 4 的子数组有： [1,4,5,2] 和 [4,5,2,3]。
在这些数组中， [4,5,2,3] 是最大的。

示例 3:

输入: nums = [1,4,5,2,3], k = 1
输出: [5]

 

提示：

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • nums 中的所有整数都是不同的。

 

进阶：如果允许 nums 中存在相同元素，你该如何解决该问题？

解法

方法一：模拟

思考

长度为 \(k\) 的子数组中，字典序最大者由其第一个元素决定，因为数组元素互不相同。

合法起点落在 \([0,n-k]\)。在该区间取最大值的下标 \(i\)，子数组即为 \(nums[i..i+k)\)。一次遍历即可。

数组中所有整数都不同，我们可以先在 \([0,..n-k]\) 范围内找到最大的元素的下标，然后从该下标开始取 \(k\) 个元素即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组的长度。忽略答案的空间消耗，空间复杂度 \(O(1)\)。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int[] largestSubarray(int[] nums, int k) {
        int j = 0;
        for (int i = 1; i < nums.length - k + 1; ++i) {
            if (nums[j] < nums[i]) {
                j = i;
            }
        }
        return Arrays.copyOfRange(nums, j, j + k);
    }
}

1
2
3
4
5
6
7
class Solution {
public:
    vector<int> largestSubarray(vector<int>& nums, int k) {
        auto i = max_element(nums.begin(), nums.end() - k + 1);
        return {i, i + k};
    }
};

1
2
3
4
5
6
7
8
9
func largestSubarray(nums []int, k int) []int {
    j := 0
    for i := 1; i < len(nums)-k+1; i++ {
        if nums[j] < nums[i] {
            j = i
        }
    }
    return nums[j : j+k]
}

1
2
3
4
5
6
7
8
9
function largestSubarray(nums: number[], k: number): number[] {
    let j = 0;
    for (let i = 1; i < nums.length - k + 1; ++i) {
        if (nums[j] < nums[i]) {
            j = i;
        }
    }
    return nums.slice(j, j + k);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn largest_subarray(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut j = 0;
        for i in 1..=nums.len() - (k as usize) {
            if nums[i] > nums[j] {
                j = i;
            }
        }
        nums[j..j + (k as usize)].to_vec()
    }
}

评论