class Solution {
public:
int maxSubarrayLength(vector<int>& nums) {
}
};
2863. 最长半递减数组
给定一个整数数组 nums。
返回 nums 的 最长半递减子数组 的长度，如果没有这样的子数组则返回 0。
示例 1：
输入： nums = [7,6,5,4,3,2,1,6,10,11] 输出： 8 解释： 取子数组 [7,6,5,4,3,2,1,6]。 第一个元素是 7，最后一个元素是 6，因此满足条件。 因此，答案是子数组的长度，即 8。 可以证明，在给定条件下，没有长度大于 8 的子数组。
示例 2：
输入： nums = [57,55,50,60,61,58,63,59,64,60,63] 输出： 6 解释： 取子数组 [61,58,63,59,64,60]. 第一个元素是 61，最后一个元素是 60，因此满足条件。 因此，答案是子数组的长度，即 6。 可以证明，在给定条件下，没有长度大于 6 的子数组。
示例 3:
输入： nums = [1,2,3,4] 输出： 0 解释： 由于给定数组中没有半递减子数组，答案为 0。
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 96 ms, 内存消耗: 9.9 MB, 提交时间: 2023-10-16 21:07:20
func maxSubarrayLength(nums []int) int {
ans := 0
st := []int{0}
for i := 1; i < len(nums); i++ {
if nums[i] > nums[st[len(st)-1]] {
st = append(st, i)
} else if nums[i] != nums[st[len(st)-1]] {
id := sort.Search(len(st), func(j int) bool {
return nums[st[j]] > nums[i]
})
ans = max(ans, i - st[id] + 1)
}
}
return ans
}
func max(a, b int) int { if a < b { return b }; return a }
java 解法, 执行用时: 106 ms, 内存消耗: 58.8 MB, 提交时间: 2023-10-16 21:06:09
class Solution {
public int maxSubarrayLength(int[] nums) {
int n = nums.length;
Integer[] sorts = new Integer[n];
for(int i = 0; i < n; i++) sorts[i] = i;
Arrays.sort(sorts,(a,b)->nums[a]==nums[b]?b-a:nums[b]-nums[a]);
int p = n;
int ans = 0;
for(int i = 0; i < n; i++){
p = Math.min(p,sorts[i]);
if(nums[sorts[i]]!=nums[p])ans = Math.max(ans,sorts[i]-p+1);
}
return ans;
}
}
python3 解法, 执行用时: 420 ms, 内存消耗: 45.7 MB, 提交时间: 2023-10-16 21:05:50
class Solution:
def maxSubarrayLength(self, nums: List[int]) -> int:
dc, res, mx = {}, 0, -1
for i, v in enumerate(nums):
if v in dc: dc[v][1] = i
else: dc[v] = [i,i]
for i in sorted(dc): res, mx = max(res, mx - dc[i][0] + 1), max(mx, dc[i][1])
return res