Next Greater Element I

Q: מהי סיבוכיות הזמן של Next Greater Element I?

פתרון המחסנית המונוטונית פועל בזמן O(n + m) , כאשר n הוא האורך של nums2 ו- m הוא האורך של nums1 . כל ערך של nums2 נדחף ונשלף לכל היותר פעם אחת, וכל ערך של nums1 דורש חיפוש אחד במפה. המפה והמחסנית משתמשות במקום O(n) . סריקה ימינה מכל ערך אורכת זמן O(n·m) .

קלמחסנית מונוטונית גיבוב

+10

נתונים לך שני מערכים של מספרים שלמים שונים, nums1 ו-nums2, וכל ערך של nums1 מופיע גם ב-nums2. האיבר הגדול הבא של ערך x הוא הערך הראשון מימין ל-x ב-nums2 שגדול מ-x, או -1 אם אין ערך כזה.

החזר מערך שמכיל את האיבר הגדול הבא של כל ערך ב-nums1, לפי הסדר של nums1.

פונקציה

nextGreaterElement(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: הערכים שיש להשיב עליהם, כולם נמצאים ב־nums2
nums2integer-array: המערך שבו מחפשים מימין לכל ערך
מחזירהinteger-array: האיבר הבא הגדול יותר עבור כל ערך של nums1, או ‎-1, לפי הסדר של nums1

אילוצים

1 ≤ nums1.length ≤ nums2.length ≤ 10⁴
0 ≤ nums1[i], nums2[i] ≤ 10⁴
כל הערכים ב-nums1 שונים, וכל הערכים ב-nums2 שונים.
כל ערך של nums1 מופיע ב-nums2.

דוגמאות

קלט: nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
פלט: [8, -1, 6]
הסבר: אחרי ה־3 ב־nums2 באים 8 ו־2, ו־8 הוא הראשון שגדול מ־3. רק 2 מופיע אחרי 8, לכן 8 מקבל ‎-1. הערך שמופיע מיד אחרי 1 הוא 6, שכבר גדול יותר.

קלט: nums1 = [5, 2]nums2 = [2, 9, 5, 4]
פלט: [-1, 9]
הסבר: רק 4 מופיע אחרי 5, ו-4 קטן ממנו, לכן 5 מקבל ‎-1. הערך שמופיע מיד אחרי 2 הוא 9. התשובות מופיעות לפי הסדר של nums1, ולא לפי הסדר של nums2.

+14 בדיקות נסתרות בשליחה

שאלת המשך

עבור כל מיקום של nums2, האם תוכל להחזיר כמה צעדים ימינה נמצא האיבר הבא הגדול ממנו, באותו מעבר יחיד?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

עבור ערך אחד, התשובה היא סריקה ימינה ממנו, אבל סריקה עבור כל ערך ב־nums1 עולה עד nums1.length × nums2.length צעדים. התשובות תלויות רק ב־nums2, לכן אפשר למצוא בבת אחת את האיבר הגדול הבא עבור כל ערך ב־nums2 באמצעות מחסנית מונוטונית, לשמור אותם במפת גיבוב ולענות עבור nums1 באמצעות חיפוש.

מצא כל ערך וסרוק ימינה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

פעלו לפי ההגדרה. עבור ערך x מתוך nums1, עברו על nums2 עד שתגיעו אל x. לאחר מכן המשיכו לעבור ועצרו בערך הראשון שגדול מ־x. אם תגיעו לסוף ולא תמצאו כזה, התשובה היא ‎-1.

זה נכון כי הסריקה עוברת לפי הסדר על הערכים שמימין ל־x, ולכן הערך הגדול הראשון שהיא פוגשת הוא הערך הגדול הראשון שקיים שם.

השיטה איטית כשהתשובות רחוקות או חסרות. אם nums2 בסדר יורד, אף סריקה לא מוצאת ערך גדול יותר, וכל ערך של nums1 נסרק עד הסוף. עם m ערכים ב־nums1 ו־n ב־nums2, מדובר בעד m × n צעדים: ‎10^8 כאשר שני המערכים מכילים 10^4 ערכים. כל סריקה גם עוברת שוב על אזורים שסריקות קודמות כבר עברו בהם.

אלגוריתם

עבור בלולאה על כל ערך x של nums1.
מצא את האינדקס j שבו nums2[j] שווה ל-x.
סרוק את nums2 החל מ-j+1 ועצור בערך הראשון שגדול מ-x.
הוסף את הערך הזה, או ‎-1 אם הסריקה הגיעה לסוף.
החזר את התשובות שנאספו.

def nextGreaterElement(nums1, nums2):
    result = []
    for x in nums1:
        j = 0
        while nums2[j] != x:
            j += 1
        answer = -1
        for k in range(j + 1, len(nums2)):
            if nums2[k] > x:
                answer = nums2[k]
                break
        result.append(answer)
    return result

מחסנית מונוטונית ומפת גיבוב

האינטואיציה

הפכו את השאלה. במקום לשאול, עבור כל ערך, מה בא אחריו, עברו על nums2 פעם אחת ותנו לכל ערך חדש לענות עבור הערכים הקודמים שהוא גדול מהם. השאירו את הערכים שעדיין אין להם תשובה במחסנית. כשערך מגיע, הוציאו מהמחסנית כל ערך קטן יותר שבראשה: הערך החדש הוא הערך הגדול הראשון שמימינו, ולכן הוא התשובה עבורם. לאחר מכן דחפו את הערך החדש, שעדיין ממתין לתשובה משלו.

עברו על nums2 = [1, 6, 3, 8, 2]. דחפו את 1. ואז מגיע 6 וגובר על 1, ולכן 1 ממופה ל־6; דחפו את 6. ואז מגיע 3, הוא אינו גובר על 6, ודוחפים אותו לראש המחסנית: המחסנית היא [6, 3]. ואז 8 מוציא את 3 ואת 6, ולכן שניהם ממופים ל־8; דחפו את 8. ואז דוחפים את 2. בסוף המחסנית היא [8, 2], ולשני הערכים האלה אין תשובה. עבור nums1 = [3, 8, 1] המיפוי נותן [8, -1, 6].

המחסנית תמיד מסודרת בסדר יורד מלמטה למעלה, כי דוחפים ערך רק לאחר שכל הערכים הקטנים ממנו שמעליו הוצאו. לכן צריך לבדוק רק את ראש המחסנית. ערך יוצא מהמחסנית ברגע שהערך הגדול הראשון מופיע, ולכן התשובה ששומרים היא הערך הראשון, ולא הערך הגדול ביותר.

כל ערך של nums2 נדחף פעם אחת ונשלף לכל היותר פעם אחת, ולכן הלולאה הפנימית מבצעת לכל היותר n שליפות בסך הכול לאורך כל המעבר. יחד עם m החיפושים, זמן הריצה הוא O(n + m). המפה היא שמקשרת בין שני המערכים: הערכים שונים זה מזה, ולכן ערך יכול לשמש כמפתח בטוח, אף שהוא נמצא במיקומים שונים ב־nums1 וב־nums2. הפתרונות ב־C וב־R משתמשים במערך של 10^4+1 תאים, שבו ערך משמש כאינדקס, בתור המפה; זה עובד כי אף ערך אינו גדול מ־10^4.

אלגוריתם

יוצרים מפה ריקה ומחסנית ריקה.
עבור כל ערך ב-nums2, מוציאים מהראש של המחסנית כל ערך קטן יותר וממפים אותו לערך הנוכחי.
דוחפים את הערך הנוכחי למחסנית.
עבור כל ערך ב-nums1, מחזירים את התשובה הממופה שלו, או ‎-1 אם אין כזו.

def nextGreaterElement(nums1, nums2):
    next_greater = {}
    stack = []  # values still waiting for a greater one, decreasing from bottom to top
    for value in nums2:
        # value is the first greater value to the right of every smaller value on the stack.
        while stack and stack[-1] < value:
            next_greater[stack.pop()] = value
        stack.append(value)
    # Whatever is still on the stack has no greater value to its right.
    return [next_greater.get(x, -1) for x in nums1]

מלכודות ומקרי קצה

קוד המחסנית עצמה קצר; הטעויות נוגעות למה שרושמים והיכן מחפשים.

רישום הערך הגדול ביותר מימין במקום הערך הראשון שגדול יותר. ב־nums2 = [3, 5, 1, 2, 4, 9, 0] התשובה עבור 1 היא 2, ולא 9.
החזרת התשובות בסדר של nums2, או עבור כל ערך של nums2. בתוצאה יש איבר אחד לכל ערך של nums1, לפי הסדר שלהם.
החזרת אינדקס במקום ערך. הבעיה מבקשת את הערך הגדול עצמו.
קריאת nums2 באינדקס שבו ערך מופיע ב־nums1. אותו ערך נמצא במיקומים שונים בשני המערכים; יש למצוא אותו לפי הערך, ולשם כך נועדה המפה.
שכחת הערכים שנותרו במחסנית בסוף. הם לא נתקלו בערך גדול יותר, ולכן התשובה עבורם היא -1; חיפוש במפה ללא ערך ברירת מחדל נכשל או לא מחזיר דבר עבורם.
חיפוש שמאלה, או חזרה לתחילת nums2. רק ערכים שמימין נחשבים, והמערך אינו מעגלי.

שאלות נפוצות4

מהי סיבוכיות הזמן של Next Greater Element I?

פתרון המחסנית המונוטונית פועל בזמן O(n + m), כאשר n הוא האורך של nums2 ו-m הוא האורך של nums1. כל ערך של nums2 נדחף ונשלף לכל היותר פעם אחת, וכל ערך של nums1 דורש חיפוש אחד במפה. המפה והמחסנית משתמשות במקום O(n). סריקה ימינה מכל ערך אורכת זמן O(n·m).

מהי מחסנית מונוטונית?

זוהי מחסנית שהערכים בה נשארים ממוינים מלמטה למעלה, במקרה הזה בסדר יורד. לפני שדוחפים ערך חדש, שולפים את כל הערכים שיפרו את הסדר, והשליפות האלה הן המקום שבו מתבצעת העבודה: כל ערך שנשלף מצא את הערך הגדול ממנו הראשון מימין. היא פותרת שאלות כמו הערך הגדול הבא, הערך הקטן הבא ושאלות דומות בזמן לינארי.

למה Next Greater Element I זקוק למפת גיבוב?

המעבר על המחסנית מפיק תשובות לפי הסדר שבו הערכים יוצאים מהמחסנית, כשהמפתחות הם הערכים של nums2. הפלט חייב להתאים לסדר של nums1, שבו אותם ערכים נמצאים במיקומים אחרים. מכיוון שכל הערכים שונים, מיפוי מערך מתשובה מקשר בין שני המערכים באמצעות חיפוש בזמן קבוע לכל ערך.

מה משתנה אם nums2 הוא מעגלי?

לאחר מכן, החיפוש אחר ערך גדול יותר יכול להימשך מתחילת המערך. בצעו את אותה סריקה עם מחסנית על המערך פעמיים, באמצעות האינדקס i % n עבור i מ-0 עד 2n-1, ודחפו ערכים למחסנית רק במהלך הסיבוב הראשון. לערכים שנותרו במחסנית אחרי שני הסיבובים אין ערך גדול יותר בשום מקום, ולכן התשובה עבורם היא -1.

Python

def nextGreaterElement(nums1, nums2):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums1 = [3, 8, 1]
nums2 = [1, 6, 3, 8, 2]

צפוי

[8, -1, 6]