跳转至

3912. 数组中的有效元素

题目描述

给你一个整数数组 nums。

如果元素 nums[i] 满足以下 至少一个 条件，则认为它是 有效 元素：

  • 它 严格大于 其左侧的所有元素。
  • 它 严格大于 其右侧的所有元素。

第一个元素和最后一个元素始终有效。

返回所有有效元素组成的数组，顺序与它们在 nums 中出现的顺序相同。

 

示例 1：

输入： nums = [1,2,4,2,3,2]

输出： [1,2,4,3,2]

解释：

  • nums[0] 和 nums[5] 始终有效。
  • nums[1] 和 nums[2] 都严格大于其左侧的所有元素。
  • nums[4] 严格大于其右侧的所有元素。
  • 因此，答案为 [1, 2, 4, 3, 2]。

示例 2：

输入： nums = [5,5,5,5]

输出： [5,5]

解释：

  • 第一个元素和最后一个元素始终有效。
  • 其他元素既不严格大于其左侧的所有元素，也不严格大于其右侧的所有元素。
  • 因此，答案为 [5, 5]。

示例 3：

输入： nums = [1]

输出： [1]

解释：

由于数组中只有一个元素，它始终有效。因此，答案为 [1]。

 

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

解法

方法一：预处理数组

我们可以预处理数组，计算出每个元素右侧的最大值，记录在数组 \(\textit{right}\) 中。

然后，我们从左到右遍历数组，使用一个变量 \(\textit{left}\) 来记录当前元素左侧的最大值。对于每个元素，如果它满足以下任一条件，则将其加入答案中：

  • 它严格大于 \(\textit{left}\)。
  • 它是数组的最后一个元素。
  • 它严格大于 \(\textit{right}[i + 1]\)。

在遍历过程中，我们不断更新 \(\textit{left}\) 的值。

遍历结束后，返回答案即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def findValidElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        right = [nums[-1]] * n
        for i in range(n - 2, -1, -1):
            right[i] = max(right[i + 1], nums[i])
        left = 0
        ans = []
        for i, x in enumerate(nums):
            if x > left or i == n - 1 or x > right[i + 1]:
                ans.append(x)
            left = max(left, x)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> findValidElements(int[] nums) {
        int n = nums.length;
        int[] right = new int[n];
        right[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], nums[i]);
        }
        int left = 0;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (x > left || i == n - 1 || x > right[i + 1]) {
                ans.add(x);
            }
            left = Math.max(left, x);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> findValidElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> right(n);
        right[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            right[i] = max(right[i + 1], nums[i]);
        }
        int left = 0;
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (x > left || i == n - 1 || x > right[i + 1]) {
                ans.push_back(x);
            }
            left = max(left, x);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func findValidElements(nums []int) []int {
    n := len(nums)
    right := make([]int, n)
    right[n-1] = nums[n-1]
    for i := n - 2; i >= 0; i-- {
        right[i] = max(right[i+1], nums[i])
    }
    left := 0
    ans := []int{}
    for i, x := range nums {
        if x > left || i == n-1 || x > right[i+1] {
            ans = append(ans, x)
        }
        left = max(left, x)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function findValidElements(nums: number[]): number[] {
    const n = nums.length;
    const right = new Array(n);
    right[n - 1] = nums[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        right[i] = Math.max(right[i + 1], nums[i]);
    }
    let left = 0;
    const ans: number[] = [];
    for (let i = 0; i < n; i++) {
        const x = nums[i];
        if (x > left || i === n - 1 || x > right[i + 1]) {
            ans.push(x);
        }
        left = Math.max(left, x);
    }
    return ans;
}

评论