Largest Rectangle in Histogram

Q: מהי סיבוכיות הזמן של Largest Rectangle in Histogram?

פתרון המחסנית המונוטונית פועל בזמן O(n) ומשתמש ב־ O(n) מקום נוסף. כל אינדקס נדחף פעם אחת ונשלף פעם אחת, וכל שליפה דורשת כמות קבועה של עבודה. בדיקת כל רצף של עמודות אורכת O(n²) זמן, כ־2 × 10^8 צעדים עבור 2 × 10^4 עמודות.

קשהמחסנית מונוטונית

+10

היסטוגרמה היא שורה של עמודות צמודות זו לזו ללא רווחים, שכל אחת מהן ברוחב יחידה אחת: heights[i] הוא הגובה של עמודה i. מלבן בתוכה מכסה רצף של עמודות סמוכות, וגובהו אינו יכול לעלות על גובה העמודה הנמוכה ביותר ברצף הזה.

החזירו את השטח הגדול ביותר שמלבן כזה יכול לכסות.

פונקציה

largestRectangleArea(heights: integer-array) → integer

heightsinteger-array: גובהו של כל עמודה, משמאל לימין
מחזירהinteger: השטח של המלבן הגדול ביותר שנכנס להיסטוגרמה

אילוצים

1 ≤ heights.length ≤ 2 × 10⁴
0 ≤ heights[i] ≤ 10⁵
כל עמודה היא ברוחב של יחידה אחת, ולכן מלבן מעל העמודות i עד j הוא ברוחב של j-i+1 יחידות.

דוגמאות

קלט: heights = [2, 5, 6, 3, 4, 1]
פלט: 12
הסבר: כל ארבעת העמודות 5, 6, 3 ו-4 הן בגובה 3 לפחות, ולכן מלבן בגובה 3 משתרע על פניהן: 3 × 4 = 12. שתי העמודות הגבוהות ביותר, 5 ו-6, נותנות רק 5 × 2 = 10.

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

שאלת המשך

נניח שלכל עמודה יש רוחב משלה, הנתון במערך שני. מה משתנה בפתרון המחסנית במעבר יחיד?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

נסו כל ריצה עם מינימום מצטבר

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

האינטואיציה

מלבן מכסה רצף של עמודות סמוכות מ־start עד end, וגובהו מוגבל לגובה העמודה הנמוכה ביותר ברצף. לכן ננסה כל רצף. נקבע את start, ואז נגדיל את end בעמודה אחת בכל פעם ונשמור את הגובה הנמוך ביותר שראינו עד כה. למלבן הטוב ביותר ברצף הזה יש שטח lowest × (end-start+1).

ב־[2, 5, 6, 3, 4, 1], נתחיל ב־5. הרצפים נותנים 5 × 1 = 5, אחר כך 5 × 2 = 10 עם ה־6, אחר כך 3 × 3 = 9 כשה־3 מצטרף, 3 × 4 = 12 עם ה־4, ו־1 × 5 = 5 עם ה־1. התשובה היא 12. עדכון lowest ככל שהרצף גדל שומר על כל שלב ב־O(1), כך שלא צריך לסרוק מחדש את הרצף כדי למצוא את המינימום שלו.

הפתרון נכון כי כל מלבן נמצא מעל רצף כלשהו, ועבור רצף קבוע המלבן הגבוה ביותר שמתאים הוא בדיוק בגובה העמודה הנמוכה ביותר. הוא איטי כי יש n(n+1)/2 רצפים: כ־2 × 10^8 עבור 2 × 10^4 עמודות, ומספר זה אינו תלוי כלל בגבהים. רוב הרצפים האלה נקטעים על ידי עמודה נמוכה הרבה לפני סופם, ובכל זאת כוח גס ממשיך להאריך אותם.

אלגוריתם

הגדר את best ל־0.
עבור כל start, הגדר את lowest ל־heights[start].
עבור כל end מ־start ועד למוט האחרון, הנמך את lowest ל־heights[end] אם המוט הזה נמוך יותר.
עדכן את best באמצעות lowest × (end-start+1).
החזר את best.

def largestRectangleArea(heights):
    n = len(heights)
    best = 0
    for start in range(n):
        lowest = heights[start]
        for end in range(start, n):
            # The rectangle over start..end is as tall as the lowest bar in it.
            lowest = min(lowest, heights[end])
            best = max(best, lowest * (end - start + 1))
    return best

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

האינטואיציה

הפכו את החיפוש. במלבן הטוב ביותר, לפחות עמודה אחת שמתחתיו גבוהה בדיוק כמו המלבן; אחרת אפשר היה להגביה את המלבן. לכן התשובה היא הטוב ביותר, מבין כל העמודות i, של מלבן שגובהו בדיוק heights[i] והוא מתפרש לרוחב המרבי האפשרי. הוא מתפרש עד שהוא פוגש עמודה נמוכה ממנו ממש בכל צד. נסמן את האינדקסים שלהן ב-left[i] וב-right[i], ונשתמש ב-‎-1 וב-n כשאין עמודה כזאת. המלבן מכסה את העמודות שביניהן, לא כולל אותן: רוחב right[i]-left[i]-1. כך יש n מועמדות במקום n²/2.

כדי למצוא את left[i] לכל עמודה, עוברים משמאל לימין עם מחסנית של אינדקסים שגובהי העמודות שלהם עולים ממש מתחתית המחסנית לראשה. כשעמודה i מגיעה, מוציאים מהמחסנית כל אינדקס שהעמודה שלו גבוהה לפחות כמו heights[i]. העמודות האלה לעולם לא יוכלו להיות העמודה הנמוכה הקרובה ביותר עבור i או עבור עמודה כלשהי אחריה, כי i קרובה יותר ואינה גבוהה יותר. מה שנשאר בראש המחסנית הוא העמודה הנמוכה הקרובה ביותר משמאל. לאחר מכן דוחפים את i למחסנית. אותו מעבר מימין לשמאל נותן את right[i].

עבור [2, 5, 6, 3, 4, 1] המעברים נותנים left = [-1, 0, 1, 0, 3, -1] ו-right = [5, 3, 3, 5, 5, 6]. העמודה בגובה 3 באינדקס 3 נעצרת על ידי ה-2 באינדקס 0 וה-1 באינדקס 5, ולכן המלבן שלה הוא 3 × (5-0-1) = 12. ה-6 תחומה על ידי שכנותיה, ומניבה רק 6 × 1.

כל אינדקס נדחף פעם אחת ומוצא מהמחסנית לכל היותר פעם אחת בכל מעבר, לכן שני המעברים הם O(n), אף שעמודה אחת עשויה להוציא עמודות רבות מהמחסנית. המחיר הוא שתי מערכים נוספים.

אלגוריתם

עבור משמאל לימין עם מחסנית ריקה. עבור כל i, הוצא מהמחסנית כל עוד המוט שבראשה גבוה לפחות כמו heights[i]; קבע את left[i] לערך שבראש המחסנית, או ל־-1 אם המחסנית ריקה; דחוף את i למחסנית.
עבור מימין לשמאל באותה דרך כדי למלא את right[i], תוך שימוש ב־n כשהמחסנית ריקה.
עבור כל i, חשב את heights[i] × (right[i]-left[i]-1).
החזר את השטח הגדול ביותר מביניהם.

def largestRectangleArea(heights):
    n = len(heights)
    left = [-1] * n  # index of the nearest shorter bar on the left, or -1
    right = [n] * n  # index of the nearest shorter bar on the right, or n
    stack = []  # indices whose heights rise strictly from bottom to top
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    best = 0
    for i in range(n):
        # Bar i is the lowest bar of everything strictly between left[i] and right[i].
        best = max(best, heights[i] * (right[i] - left[i] - 1))
    return best

מעבר אחד עם מחסנית מונוטונית

האינטואיציה

המעבר משמאל לימין כבר רואה כל גבול ימני; הוא משליך אותו. כשעמודה i מוציאה מהמחסנית את העמודה t, heights[i] אינה גבוהה יותר מ-heights[t], ולכן i הוא המקום שבו המלבן של t מסתיים מימין. והאינדקס שנמצא מתחת ל-t במחסנית הוא המקום שבו הוא מסתיים משמאל. לכן חשבו את שטח המלבן ברגע שמוציאים אותו מהמחסנית: heights[t] × (i - below - 1), כאשר below הוא ראש המחסנית החדש, או -1 אם המחסנית ריקה כעת.

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

עברו על [2, 5, 6, 3, 4, 1]. דוחפים את 2, 5 ו-6: המחסנית מכילה את האינדקסים [0, 1, 2]. ה-3 באינדקס 3 מוציא מהמחסנית את ה-6 (שטח 6 × (3-1-1) = 6) ואת ה-5 (שטח 5 × (3-0-1) = 10), ואז נעצר ב-2 ונדחף למחסנית. דוחפים את ה-4. ה-1 באינדקס 5 מוציא מהמחסנית את ה-4 (שטח 4), ואז את ה-3, שהמלבן שלו משתרע מאינדקס 1 עד 4: 3 × (5-0-1) = 12. הוא מוציא מהמחסנית גם את ה-2 (2 × 5 = 10; המחסנית ריקה, ולכן הרוחב הוא 5). ה-0 הסוגר מוציא מהמחסנית את ה-1 (1 × 6 = 6). הערך המרבי הוא 12.

הוצאה מהמחסנית בתנאי >= פירושה שעמודה שווה יכולה לעצור עמודה מוקדם. זה בטוח: העמודה השווה תופסת את מקומה במחסנית, יורשת את אותו גבול שמאלי, וכשמוציאים אותה מהמחסנית מאוחר יותר, המלבן שלה מכסה את כל הרצף. ב-[3, 3, 3, 3] שלושת מופעי ה-3 הראשונים מתעדים רוחבים 1, 2 ו-3, והאחרון יוצא מהמחסנית על ידי ה-0 הסוגר ברוחב 4, ומתקבל 12.

אלגוריתם

התחל עם מחסנית ריקה של אינדקסים ועם best = 0.
עבור i מ־0 עד n, הגדר את הגובה הנוכחי כ־heights[i], או 0 כאשר i = n.
כל עוד המוט שבראש המחסנית גבוה לפחות כמו הגובה הנוכחי, הוצא אותו מהמחסנית בתור t; הרוחב הוא i - below - 1, כאשר below הוא האיבר החדש בראש המחסנית או ‎-1; עדכן את best בעזרת heights[t] × width.
דחוף את i למחסנית.
החזר את best.

def largestRectangleArea(heights):
    n = len(heights)
    stack = []  # indices whose heights rise strictly from bottom to top
    best = 0
    for i in range(n + 1):
        current = heights[i] if i < n else 0  # a bar of 0 past the end empties the stack
        while stack and heights[stack[-1]] >= current:
            # Bar i stops the popped bar on the right; the bar below it stops it on the left.
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

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

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

שוכחים את המלבנים שעדיין נמצאים במחסנית. בהיסטוגרמה עולה כמו [1, 2, 3, 4, 5] לא מוציאים אף מלבן מהמחסנית בתוך הלולאה, ובלי מלבן סגירה בגובה 0 מחזירים 0 במקום 9.
מחשבים את הרוחב לפי האינדקס של המלבן שהוצא מהמחסנית. המלבן שלו מתחיל מיד אחרי המלבן שמתחתיו במחסנית, ולא במיקומו שלו: ב־[2, 5, 6, 3, 4, 1] המלבן בגובה 3 באינדקס 3 משתרע על האינדקסים 1 עד 4. שימוש ב־i - t נותן 2 במקום 4.
משתמשים ברוחב שגוי כשהמחסנית ריקה אחרי הוצאה ממנה. המלבן שהוצא הוא הנמוך ביותר עד כה, ולכן המלבן שלו מגיע עד לאינדקס 0 והרוחב הוא i. ב־[2, 1, 2] המלבן בגובה 1 משתרע על פני שלושת המלבנים, ושטחו 3.
עוצרים במלבנים שווים משני הצדדים בגרסה של שני המעברים. במקרה כזה, ב־[3, 3, 3, 3] כל מלבן מקבל רוחב 1 ומחזירים 3 במקום 12. מוציאים מהמחסנית כשמתקיים >=, כך שהגבולות יהיו מלבנים נמוכים יותר ממש.
מניחים שהמלבן הגבוה ביותר או הטווח הרחב ביותר יניבו את התוצאה. ב־[2, 5, 6, 3, 4, 1] לא הגובה 6 ולא הרוחב המלא של 6 מלבנים נותנים את התשובה; הגובה שבאמצע על פני רוחב בינוני הוא שנותן אותה.
גלישת מספרים. שטח יכול להגיע כאן ל־10^5 × 2 × 10^4 = 2 × 10^9, ועדיין להתאים למספר שלם signed של 32 סיביות; בגבולות גדולים יותר, בצעו את הכפל ב־64 סיביות.

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

מהי סיבוכיות הזמן של Largest Rectangle in Histogram?

פתרון המחסנית המונוטונית פועל בזמן O(n) ומשתמש ב־O(n) מקום נוסף. כל אינדקס נדחף פעם אחת ונשלף פעם אחת, וכל שליפה דורשת כמות קבועה של עבודה. בדיקת כל רצף של עמודות אורכת O(n²) זמן, כ־2 × 10^8 צעדים עבור 2 × 10^4 עמודות.

למה מודדים את המלבן של עמודה כשהיא נשלפת?

עמודה נשלפת על ידי העמודה הראשונה מימינה שאינה גבוהה ממנה, ולכן שם המלבן שלה מסתיים מימין. האינדקס שמתחתיה במחסנית מציין את העמודה הנמוכה הקרובה ביותר משמאלה, ולכן שם הוא מסתיים משמאל. ברגע השליפה שני הקצוות ידועים, והשטח הוא height × (i - below - 1).

האם אפשר לפתור את בעיית המלבן הגדול ביותר בהיסטוגרמה באמצעות הפרד ומשול?

כן. המוט הנמוך ביותר בכל הטווח נמצא מתחת למלבן הטוב ביותר, ששטחו הוא lowest × width, או שהוא מחלק את הטווח לחלק שמאלי ולחלק ימני, שאותם פותרים בנפרד. בסריקה ליניארית למציאת המינימום, הסיבוכיות היא O(n log n) בקלט אקראי, אבל O(n²) בקלט ממוין; עץ מקטעים למציאת מינימום בטווחים מבטיח סיבוכיות של O(n log n) תמיד. המחסנית פשוטה ומהירה יותר.

כיצד משתמשים באלגוריתם המלבן הגדול ביותר בהיסטוגרמה כדי למצוא את המלבן המקסימלי ברשת של 0 ו־1?

עבור על הרשת שורה אחר שורה, ושמור עבור כל עמודה כמה 1-ים רצופים מסתיימים בשורה הנוכחית; 0 מאפס את הספירה. הספירות של כל שורה יוצרות היסטוגרמה, והמלבן הגדול ביותר של 1-ים שמסתיים בשורה הזאת הוא המלבן הגדול ביותר בהיסטוגרמה הזאת. הרצת המחסנית פעם אחת לכל שורה פותרת את בעיית הרשת בזמן O(rows × cols).

Python

def largestRectangleArea(heights):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

heights = [2, 5, 6, 3, 4, 1]

צפוי

Largest Rectangle in Histogram

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסו כל ריצה עם מינימום מצטבר

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

מעבר אחד עם מחסנית מונוטונית

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

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

בעיות דומות