Tìm phần tử trong mảng có giá trị lớn hơn tất cả các phần tử phía bên phải

Viết chương trình tìm in tất cả các phần tử trong mảng nếu nó lớn hơn tất cả các phần tử phía bên phải nó.

Cho ví dụ 

Input: arr[] = {5, 10, 6, 7, 4, 5, 2}, n = 7

Output: 10, 7, 5, 2

Cách 1: Sử dụng 2 vòng loop

Có lẽ đây là cách chúng ta nghĩ ra đầu tiên =). Chúng ta sử dụng 2 vòng loop để kiểm tra từng phần tử trong mảng arr[i] lớn hơn tất cả các phần tử bên phải (arr[i] >= all(arr[i + 1 -> n – 1]) thì in ra kết quả.

public class Main {

    // Use two loop
    public static void printLeadersTwoLoop(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            int j;
            for (j = i + 1; j < n; j++) {
                if (arr[i] <= arr[j])
                    break;
            }
            if (j == n)
                System.out.print(arr[i] + " ");
        }

    }

    public static void main(String[] args) {
        int[] arr = {5, 10, 6, 7, 4, 5, 2};
        printLeadersTwoLoop(arr, arr.length);
    }
}

Output: 10 7 5 2

Độ phức tạp: O(n²)

Cách 2: Duyệt từ bên phải

Để cải tiến hơn một tí, chúng ta thấy phần tử cuối cùng luôn là phần tử lớn hơn tất cả các phần tử bên phải(vì có ai nằm bên phải nó đâu 😆 ).  Ủa vậy nếu như tui duyệt từ phải qua rồi lưu lại giá trị lớn nhất trong khoảng đã duyệt thì sao nhỉ. À vậy phần tử nào lớn hơn nó thì là lớn hơn tất cả các phần tử phía bên phải rồi =)). 

Các bước thực hiện:

B1: Khởi tạo  max = arr[n – 1],  in phần từ arr[n – 1] B2: Duyệt mảng từ n – 2 đến 0, với mỗi phần tử arr[i]        If arr[i] > max thì            Gán max = arr[i]           In arr[i]

 

public class Main {

    // scan from right
    public static void printLeaderScanFromRight(int[] arr, int n) {
        int leader = arr[n - 1];
        // The last elememt is always leader
        System.out.print(leader + " ");

        for (int i = n - 1; i >= 0; i--) {
            if (arr[i] > leader) {
                System.out.print(arr[i] + " ");
                leader = arr[i];
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 10, 6, 7, 4, 5, 2};       
        printLeaderScanFromRight(arr, arr.length);
    }
}

Output: 2 5 7 10

Độ phức tạp: O(n)

Nếu các bạn có cách cách giải quyết khác hoặc tìm ra điểm sai thì đừng ngại mà hãy comment ý kiến cho mình biết nhé.

Full source: source

Nguồn tham khảo: geeksforgeeks