如何编写函数从数组中提取所有大于右侧全部元素的值？

嘿，这个问题挺经典的！要找出数组里所有比右侧全部元素都大的数，其实有几种不同复杂度的实现方式，我给你拆解一下：

这是最容易想到的思路：对数组里的每一个元素，都逐个检查它右侧的所有元素，如果所有右侧元素都比它小，就把它加入结果列表。

举个Python的实现例子：

def find_greater_than_right(arr):
    result = []
    n = len(arr)
    for i in range(n):
        is_greater = True
        for j in range(i+1, n):
            if arr[j] >= arr[i]:
                is_greater = False
                break
        if is_greater:
            result.append(arr[i])
    return result

# 测试示例
print(find_greater_than_right([75,47,42,56,13,55]))  # 输出 [75,56,55]
print(find_greater_than_right([16,17,14,3,14,5,2]))  # 输出 [17,14,5,2]

这种方法的时间复杂度是O(n²)，空间复杂度是O(1)（除了存储结果的数组）。适合处理小规模的数组，但如果数组很大（比如上万条数据），效率就会比较低。

这个方法能把时间复杂度降到O(n)，思路很巧妙：我们从数组的最右端开始往左走，记录当前遇到的最大值。每遇到一个元素，如果它比当前记录的最大值还大，说明它比右侧所有元素都大（因为右侧的最大值我们已经记下来了），就把它加入结果，然后更新当前最大值。最后因为我们是从右往左收集的元素，需要把结果反转一下才能得到正确的顺序。

Python实现示例：

def find_greater_than_right(arr):
    if not arr:
        return []
    result = []
    max_right = arr[-1]
    result.append(max_right)
    for num in reversed(arr[:-1]):
        if num > max_right:
            result.append(num)
            max_right = num
    return result[::-1]

# 测试示例
print(find_greater_than_right([75,47,42,56,13,55]))  # 输出 [75,56,55]
print(find_greater_than_right([16,17,14,3,14,5,2]))  # 输出 [17,14,5,2]

这个方法只需要遍历数组一次，效率极高，是处理大规模数组的首选方案。

如果之后你需要处理类似的“边界元素”问题（比如找下一个更大元素），单调栈是个很实用的工具。这里我们维护一个单调递减栈：遍历数组时，对于当前元素，弹出栈中所有比它小的元素（这些元素不可能是答案，因为当前元素在它们右侧且更大），然后把当前元素压入栈。遍历结束后，栈里剩下的元素就是所有比右侧全部元素都大的数。

Python实现示例：

def find_greater_than_right(arr):
    stack = []
    for num in arr:
        # 弹出栈中所有小于当前元素的元素
        while stack and stack[-1] < num:
            stack.pop()
        stack.append(num)
    return stack

# 测试示例
print(find_greater_than_right([75,47,42,56,13,55]))  # 输出 [75,56,55]
print(find_greater_than_right([16,17,14,3,14,5,2]))  # 输出 [17,14,5,2]

这个方法的时间复杂度也是O(n)，因为每个元素最多入栈和出栈一次。它的优势在于可以灵活扩展到其他类似的数组问题，比如需要记录元素的索引等场景。

内容的提问来源于stack exchange，提问作者RedruM