[Mảng 1 Chiều Cơ Bản]. Bài 42. Next greater element

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem source:
28Tech
Problem type
Allowed languages
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng A[] gồm N phần tử, nhiệm vụ của bạn là đối với mỗi phần tử trong mảng A[] bạn hãy tìm phần tử đầu tiên lớn hơn nó nằm ở bên phải, đối với phần tử không có phần tử lớn hơn bên phải thì in ra -1

Ví dụ : mảng A[] là {3, 8, 9, 1, 4, 2, 5} thì kết quả sẽ là 8, 9, -1, 4, 5, 5, -1.

Gợi ý : Đối với mỗi chỉ số i sử dụng 1 vòng for từ i + 1 tới cuối dãy để tìm số đầu tiên lớn hơn A[i], tìm được thì break và in ra.


Đầu vào

Dòng 1 là N : số phần tử trong mảng

Dòng 2 là N phần tử cách nhau 1 khoảng trắng


Giới hạn

1<=N<=1000

0<=A[i]<=1000


Đầu ra

In ra đáp án của bài toán


Ví dụ :

Input 01
8
53 97 89 87 17 70 27 46
Output 01
97 -1 -1 -1 70 -1 46 -1

Comments

Please read the guidelines before commenting.



  • -4
    nguyen_luong_an  commented on Dec. 18, 2024, 11:17 p.m.

    Có cách nào làm bài này nhanh hơn O(n*n) ko nhỉ mn


    • 0
      kira_yoshikage  commented on May 1, 2025, 11:03 p.m. edit 8

      hay la thu luu max cua a[n-1] den a[i] trong mang f[n] di, chung nao can hoi if(a[i]!=f[i]) la dc,luu mang f ton co O(n) cong may thu khac nua thoi(khong biet dung hay sai nhung khong can 2 vong long nhau)


      • 0
        bengokyeuanh99  commented on May 2, 2025, 7:21 a.m.

        Cách bạn nói lưu max bên phải là sai bản chất bài toán nhé 'Next greater element' yêu cầu phần tử đầu tiên lớn hơn nằm bên phải, không phải max của đoạn sau dyệt từ phải sang và dùng stack đơn điệu mới là giải pháp O(n) đúng nhá


    • 0
      rei_2412k8  commented on Jan. 23, 2025, 4:00 a.m.

      duyệt ngược từ n-2 đến 0 ấy bro, duy trì một biến max đến tìm giá trị max nằm bên phải a[i] , r so với a[i] th


      • 0
        rei_2412k8  commented on Jan. 24, 2025, 4:49 p.m.

        xl tôi nhầm


  • -8
    Itachi  commented on April 30, 2024, 12:37 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.