3912. 数组中的有效元素

English Version

题目描述

给你一个整数数组 nums。

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

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

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

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

 

示例 1：

示例 2：

示例 3：

 

提示：

• 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}$ 的长度。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}