class Solution {
public:
vector<int> largestSubarray(vector<int>& nums, int k) {
}
};
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 <= 1051 <= nums[i] <= 109nums 中的所有整数都是不同的。进阶：如果允许
nums 中存在相同元素，你该如何解决该问题？
原站题解
golang 解法, 执行用时: 96 ms, 内存消耗: 7.9 MB, 提交时间: 2023-10-15 15:29:36
func largestSubarray(nums []int, k int) []int {
n:=len(nums)
left:=0
for right:=0;right<=n-k;right++{
if nums[right]>nums[left]{
left=right
}
}
return nums[left:left+k]
}
python3 解法, 执行用时: 56 ms, 内存消耗: 28.3 MB, 提交时间: 2023-10-15 15:29:12
class Solution:
def largestSubarray1(self, nums, k):
check_num = nums[:len(nums)-k+1]
max_num = max(check_num)
count = 0
res = []
for i in range(len(check_num)):
if max_num == check_num[i]:
count += 1
res.append(nums[i:i+k])
if count == 1:
idx = check_num.index(max_num)
return nums[idx:idx+k]
else:
tmp = res[0]
for v in range(1, len(res)):
for k in range(len(v)):
if v[k] > tmp[k]:
tmp = v
break
return tmp
def largestSubarray(self, nums: List[int], k: int) -> List[int]:
l = max(nums[:-k+1]) if k!=1 else max(nums)
return nums[nums.index(l):nums.index(l)+k]
java 解法, 执行用时: 1 ms, 内存消耗: 53.4 MB, 提交时间: 2023-10-15 15:28:08
class Solution {
public int[] largestSubarray(int[] nums, int k) {
return largestSubarrayCal(nums,k);
}
//其实就是找数组倒数第k个元素前面最大值，然后复制k个元素下来就好了
//题目提示，所有元素都不相同，不用考虑相同然后复杂比较
//就是一个找最大值，一个复制元素操作而已
public int[] largestSubarrayCal(int[] nums,int k){
if(k > nums.length) return null;
if(k == nums.length) return nums;
int n = nums.length - k,i;
int maxindex = 0,max = nums[0];
for( i = 1; i <= n; i++){
if(nums[i] > max){
max = nums[i];
maxindex = i;
}
}
int[] bak = new int[k];
for(int j = maxindex;j-maxindex < k ; j++){
bak[j-maxindex] = nums[j];
}
return bak;
}
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 70.6 MB, 提交时间: 2023-10-15 15:27:39
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};
}
};