如何统计数组元素左侧更大元素数及寻找对应最大值？

Hey there! Let’s break down your two array-related questions and walk through both straightforward and optimized solutions.

1. Counting the Number of Larger Elements to the Left of a Specific Element #

Straightforward (Brute Force) Approach #

If you only need to check a single specific element, the brute force method is intuitive: iterate through all elements to the left of your target index and count how many are larger.

public static int countLargerLeft(int[] arr, int targetIdx) {
    int count = 0;
    // Loop through all elements before the target index
    for (int j = 0; j < targetIdx; j++) {
        if (arr[j] > arr[targetIdx]) {
            count++;
        }
    }
    return count;
}

• Pros: Simple to write and understand.
• Cons: Runs in O(n) time per query. If you need to check multiple elements, this adds up to O(n²) total time, which gets slow for large arrays (e.g., n > 10,000).

Optimized Approach (Fenwick Tree / Binary Indexed Tree) #

For handling multiple queries or large arrays, a Fenwick Tree lets us compute counts for all elements in O(n log n) total time. Here’s how it works:

1. Discretize the array elements (compress large values into a smaller range to fit the tree).
2. Traverse the array from left to right:
   • For each element, query the tree to find how many already-added elements are larger than it.
   • Insert the current element into the tree.

class FenwickTree {
    private int[] tree;
    
    public FenwickTree(int size) {
        tree = new int[size + 1]; // Fenwick Trees use 1-based indexing
    }
    
    // Update the tree to add an element at the given index
    public void update(int idx, int delta) {
        while (idx < tree.length) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }
    
    // Query the sum of elements from 1 to idx
    public int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
}

// Returns an array where each index holds the count of larger left elements for that position
public static int[] countLargerLeftAll(int[] arr) {
    int n = arr.length;
    int[] sortedArr = arr.clone();
    Arrays.sort(sortedArr);
    
    int[] result = new int[n];
    FenwickTree ft = new FenwickTree(n);
    
    for (int i = 0; i < n; i++) {
        // Find the rank of elements greater than arr[i]
        int upperRank = Arrays.binarySearch(sortedArr, arr[i] + 1);
        if (upperRank < 0) upperRank = -upperRank - 1;
        
        // Total elements added so far minus elements <= arr[i] = elements > arr[i]
        result[i] = i - ft.query(upperRank);
        
        // Insert current element into the tree
        int insertRank = Arrays.binarySearch(sortedArr, arr[i]);
        if (insertRank < 0) insertRank = -insertRank - 1;
        ft.update(insertRank + 1, 1);
    }
    return result;
}

2. Find the Element with the Maximum Number of Larger Left Elements (and Get That Max Count) #

Your Brute Force Solution (Completed) #

First, let’s finish the brute force code you started—it works great for small arrays:

public static int findMaxLargerLeftCount(int[] arr) {
    int n = arr.length;
    int biggest = 0;
    
    for (int i = 0; i < n; i++) {
        int num = 0;
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[i]) {
                num++;
            }
        }
        biggest = Math.max(biggest, num);
    }
    return biggest;
}

• Time Complexity: O(n²)—this will struggle with arrays larger than ~10,000 elements.

Optimized Solution (Using Fenwick Tree) #

We can reuse the countLargerLeftAll method from the first question to get all counts in O(n log n) time, then just find the maximum value in the result array:

public static int findMaxLargerLeftCountOptimized(int[] arr) {
    int[] allCounts = countLargerLeftAll(arr);
    int maxCount = 0;
    
    for (int count : allCounts) {
        if (count > maxCount) {
            maxCount = count;
        }
    }
    return maxCount;
}

Alternative Optimized Approach (Sorted List with Binary Search) #

If you prefer a simpler optimized method without a Fenwick Tree, you can maintain a sorted (descending) list and use binary search to count larger elements:

import java.util.ArrayList;
import java.util.List;

public static int findMaxLargerLeftCountWithSortedList(int[] arr) {
    int maxCount = 0;
    List<Integer> sortedDescList = new ArrayList<>();
    
    for (int num : arr) {
        // Binary search to find the first element <= num (in descending list)
        int left = 0, right = sortedDescList.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (sortedDescList.get(mid) > num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // The number of elements > num is equal to the left index
        int count = left;
        maxCount = Math.max(maxCount, count);
        
        // Insert num into the correct position to keep the list descending
        sortedDescList.add(left, num);
    }
    return maxCount;
}

• Note: This runs in O(n log n) time on average, though ArrayList insertions are O(k) for each step (where k is the current list length). For very large arrays, the Fenwick Tree method is still faster.

Hope these solutions clear things up! Feel free to ask if you want to dive deeper into any of the concepts.

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