跳转至

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

解法

方法一：哈希表 + 排序

题目实际上是求逆序对的最大长度，我们不妨用哈希表 $d$ 记录数组中每个数字 $x$ 对应的下标 $i$。

接下来，我们按照数字从大到小的顺序遍历哈希表的键，用一个数字 $k$ 维护此前出现过的最小的下标，那么对于当前的数字 $x$，我们可以得到一个最大的逆序对长度 $d[x][|d[x]|-1]-k + 1$，其中 $|d[x]|$ 表示数组 $d[x]$ 的长度，即数字 $x$ 在原数组中出现的次数，我们更新答案即可。然后，我们将 $k$ 更新为 $d[x][0]$，即数字 $x$ 在原数组中第一次出现的下标。继续遍历哈希表的键，直到遍历完所有的键。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $nums$ 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxSubarrayLength(self, nums: List[int]) -> int:
        d = defaultdict(list)
        for i, x in enumerate(nums):
            d[x].append(i)
        ans, k = 0, inf
        for x in sorted(d, reverse=True):
            ans = max(ans, d[x][-1] - k + 1)
            k = min(k, d[x][0])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int maxSubarrayLength(int[] nums) {
        TreeMap<Integer, List<Integer>> d = new TreeMap<>(Comparator.reverseOrder());
        for (int i = 0; i < nums.length; ++i) {
            d.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        int ans = 0, k = 1 << 30;
        for (List<Integer> idx : d.values()) {
            ans = Math.max(ans, idx.get(idx.size() - 1) - k + 1);
            k = Math.min(k, idx.get(0));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxSubarrayLength(vector<int>& nums) {
        map<int, vector<int>, greater<int>> d;
        for (int i = 0; i < nums.size(); ++i) {
            d[nums[i]].push_back(i);
        }
        int ans = 0, k = 1 << 30;
        for (auto& [_, idx] : d) {
            ans = max(ans, idx.back() - k + 1);
            k = min(k, idx[0]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func maxSubarrayLength(nums []int) (ans int) {
    d := map[int][]int{}
    for i, x := range nums {
        d[x] = append(d[x], i)
    }
    keys := []int{}
    for x := range d {
        keys = append(keys, x)
    }
    sort.Slice(keys, func(i, j int) bool { return keys[i] > keys[j] })
    k := 1 << 30
    for _, x := range keys {
        idx := d[x]
        ans = max(ans, idx[len(idx)-1]-k+1)
        k = min(k, idx[0])
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function maxSubarrayLength(nums: number[]): number {
    const d: Map<number, number[]> = new Map();
    for (let i = 0; i < nums.length; ++i) {
        if (!d.has(nums[i])) {
            d.set(nums[i], []);
        }
        d.get(nums[i])!.push(i);
    }
    const keys = Array.from(d.keys()).sort((a, b) => b - a);
    let ans = 0;
    let k = Infinity;
    for (const x of keys) {
        const idx = d.get(x)!;
        ans = Math.max(ans, idx.at(-1) - k + 1);
        k = Math.min(k, idx[0]);
    }
    return ans;
}

评论