Python算法效率优化：改写foo函数以实现渐近最优性能

First, let's clarify exactly what the original foo function does: it returns a list where each element at index i is the minimum value of the sublist starting at i and extending to the end of the input list.

Your two previous attempts have critical flaws:

• The recursive approach still leans on sorted (which costs O(k log k) per sublist, leading to an overall O(n² log n) runtime) and will hit recursion depth limits for large inputs like 10⁵ elements.
• The insertion sort approach modifies the original input list (breaking requirement 1) and returns a fully sorted list—this doesn't match the intended behavior of the function at all.

The Optimal O(n) Solution #

The key insight here is to traverse the input list from right to left, keeping track of the smallest value we've encountered so far. For each position i, the minimum of numbers[i:] is simply the smaller value between numbers[i] and the minimum of numbers[i+1:] (which we already calculated in the previous step).

Here's the implementation that meets all your requirements:

def foo(numbers):
    if not numbers:
        return []
    # Start with the last element (its own minimum)
    result = [numbers[-1]]
    current_min = numbers[-1]
    # Traverse from the second-last element back to the start
    for num in reversed(numbers[:-1]):
        current_min = min(num, current_min)
        result.append(current_min)
    # Reverse to get the correct left-to-right order
    return result[::-1]

Why This Works #

• Time Complexity: O(n) — we only traverse the list once, with constant-time operations per element. This will handle 10⁵ elements easily in well under 1 second.
• No Input Modification: We never alter the original numbers list; we only read values from it.
• Correctness: Let's validate against your test cases:
  1. foo(list(range(10**5))) returns a list where each element at index i is i (since the input is sorted ascending), and runs in linear time.
  2. foo([1,2,4,3]) → [1, 2, 3, 3] ✔️
  3. foo([8, 7]) → [7, 7] ✔️
  4. foo([5]) → [5] ✔️
  5. foo([3, 3, 2, 1]) → [1, 1, 1, 1] ✔️

Quick Notes #

• We handle empty input gracefully (returns an empty list).
• Reversing the result list at the end is an O(n) operation, which doesn't change the overall linear time complexity.

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