2026-08-08：数组中的有效元素。用go语言，给定一个整数序列。对于其中的任意一个数，如果它比它左边出现过的所有数都大，或者比它右边出

2026-08-08：数组中的有效元素。用go语言，给定一个整数序列。对于其中的任意一个数，如果它比它左边出现过的所有数都大，或者比它右边出现过的所有数都大，那它就符合筛选条件。另外，序列的第一个数和最后一个数无论大小都直接视为符合条件。最后，按照这些数在原序列中的出现顺序，将它们全部找出来。

1 <= nums.length <= 100。

1 <= nums[i] <= 100。

输入： 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]。

题目来自力扣3912。

该算法分两个主要阶段，通过两次遍历和辅助标记数组，找出所有符合“左侧最大”或“右侧最大”条件的有效元素。

阶段一：从右向左遍历，标记右侧最大元素

1. 1. 创建一个与输入数组nums等长的布尔数组rightValid，用于记录每个位置的元素是否严格大于它右边的所有元素。初始时所有值均为假。

2. 2. 设置一个变量mx，表示当前已经扫描过的右侧部分的最大值。由于数组元素取值范围为 1~100，将mx初始化为 0（任何元素都大于 0），这样可以正确处理数组最后一个元素。

3. 3. 从最后一个元素开始，逆序向前遍历数组：

• • 取出当前元素x。

• • 若x严格大于mx，则说明x大于它右侧所有已扫描元素，即满足“严格大于右侧所有元素”的条件，将rightValid[i]设为真；否则设为假。

• • 然后用x更新mx，使mx始终维护从当前位置到数组末尾的最大值。

4. 遍历结束后，rightValid数组的每个位置都对应原数组元素，标记了该元素是否比它右边的所有数都大。特别地，最后一个元素右侧无元素，其对应mx初始为 0，因此一定会被标记为真，符合题目“最后一个元素始终有效”的规则。

阶段二：从左向右遍历，结合左侧条件和右侧标记收集结果

1. 1. 重置mx为 0，此时mx表示当前已扫描过的左侧部分的最大值。

2. 2. 准备一个空的结果列表ans，用于按序存放有效元素。

3. 3. 从第一个元素开始，顺序向前遍历数组：

• • 取出当前元素x。

• • 判断条件：若x严格大于mx，则说明x大于它左侧所有已扫描元素，即满足“严格大于左侧所有元素”；若rightValid[i]为真，则说明x满足“严格大于右侧所有元素”。这两个条件只要满足其一，当前元素就是有效元素，将其加入ans。

• • 无论是否加入结果，都用x更新mx，使mx始终维护从数组起始到当前位置的最大值。

4. 对于第一个元素，因其左侧无元素，mx初始为 0，必然满足x > mx，因此一定会被加入结果，符合“第一个元素始终有效”的规则。

5. 遍历完成后，ans中即为所有有效元素，且保持了原数组的出现顺序。

时间复杂度分析

算法包含两次独立的线性遍历：从右向左遍历一次，从左向右遍历一次，每次仅包含常数时间的比较、赋值和更新操作。因此总的时间复杂度为O(n)，其中 n 为数组长度。

额外空间复杂度分析

除了输入数组和最终返回的结果数组外，算法额外分配了一个长度与输入相同的布尔数组rightValid，用于存储每个位置的右侧最大标记。该数组占用 O(n) 空间。过程中仅使用了常数个辅助变量（如mx、循环索引等），因此总的额外空间复杂度为O(n)。如果严格将返回结果所用的空间不计入额外空间，则依然为 O(n)。

Go完整代码如下：

package main

 import (
    "fmt"
    "slices"
)

 func findValidElements(nums []int) (ans []int) {
    // 标记严格大于其右侧所有元素的元素
    rightValid := make([]bool, len(nums))
    mx := 0
    for i, x := range slices.Backward(nums) {
        rightValid[i] = x > mx
        mx = max(mx, x)
    }

     mx = 0
    for i, x := range nums {
        if x > mx || rightValid[i] {
            ans = append(ans, x)
        }
        mx = max(mx, x)
    }
    return
}

 func main() {
    nums := []int{1, 2, 4, 2, 3, 2}
    result := findValidElements(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def findValidElements(nums):
    n = len(nums)
    rightValid = [False] * n
    mx = 0
    for i in range(n - 1, -1, -1):
        x = nums[i]
        rightValid[i] = x > mx
        mx = max(mx, x)

     mx = 0
    ans = []
    for i, x in enumerate(nums):
        if x > mx or rightValid[i]:
            ans.append(x)
        mx = max(mx, x)
    return ans

 if __name__ == "__main__":
    nums = [1, 2, 4, 2, 3, 2]
    result = findValidElements(nums)
    print(result)

C++完整代码如下：

  

  

  


 std::vector findValidElements(const std::vector& nums) {
    int n = nums.size();
    if (n == 0) return {};

     // 标记严格大于其右侧所有元素的元素
    std::vector rightValid(n, false);
    int mx = 0;
    for (int i = n - 1; i >= 0; --i) {
        int x = nums[i];
        rightValid[i] = (x > mx);
        mx = std::max(mx, x);
    }

     // 根据左侧最大值和右侧标记收集有效元素
    std::vector ans;
    mx = 0;
    for (int i = 0; i < n; ++i) {
        int x = nums[i];
        if (x > mx || rightValid[i]) {
            ans.push_back(x);
        }
        mx = std::max(mx, x);
    }
    return ans;
}

 int main() {
    std::vector nums = {1, 2, 4, 2, 3, 2};
    std::vector result = findValidElements(nums);
    for (int x : result) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。