Longest Increasing Path in a Matrix

+10

נתון לך matrix, רשת של מספרים שלמים עם m שורות ו-n עמודות, כרשימה של שורות. מסלול עובר מתא לתא, צעד אחד למעלה, למטה, שמאלה או ימינה בכל פעם (ללא צעדים באלכסון וללא מעבר מעבר לקצוות), ובכל צעד חייבים לנחות על ערך גדול ממש. החזר את מספר התאים במסלול הארוך ביותר כזה. תא יחיד בפני עצמו הוא מסלול של תא אחד.

פונקציה

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: רשת הערכים, כרשימה של שורות באורך שווה
מחזירהinteger: מספר התאים במסלול העולה ממש הארוך ביותר

אילוצים

1 ≤ m, n ≤ 100, כאשר m = matrix.length ו-n = matrix[i].length
לכל שורה יש אותו אורך n.
0 ≤ matrix[i][j] ≤ 2³¹-1

דוגמאות

קלט: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
פלט: 7
הסבר: המסלול 3, 4, 5, 6, 7, 8, 9 יורד לאורך העמודה הימנית, פונה שמאלה לאורך השורה התחתונה, עולה לאורך העמודה האמצעית ופונה שמאלה אל ה־9 שבפינה: 7 תאים. הערך הקטן ביותר מצליח פחות: מ־1 המסלולים הטובים ביותר הם 1, 2, 7, 8, 9 ו־1, 6, 7, 8, 9, עם 5 תאים בכל אחד.

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

שאלת המשך

האם תוכל גם להחזיר את התאים של אחד המסלולים הארוכים ביותר, ולא רק את אורכו?

פתרון

ציירו חץ מכל תא אל כל תא שכן שמכיל ערך גדול יותר. הערכים עולים לאורך כל חץ, ולכן שום שרשרת חצים לא יכולה לחזור לנקודת ההתחלה: הרשת היא גרף מכוון חסר מעגלים, והמשימה היא למצוא את המסלול הארוך ביותר בו. בגרף כללי, השאלה הזאת חסרת פתרון מעשי עבור קלטים גדולים, אבל בהיעדר מעגלים, המסלול הארוך ביותר מתא תלוי רק באותו תא, ולכן מחשבים אותו פעם אחת לכל תא, והבעיה כולה מצטמצמת ל־O(m × n). חיפוש עומק תחילה עם שמירת תוצאות בזיכרון מחשב אותו מלמעלה למטה; קילוף הרשת מהפסגות שלה, כלומר אלגוריתם קאהן בסדר הפוך, מחשב אותו מלמטה למעלה.

עקבו אחר כל מסלול עולה

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

האינטואיציה

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

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

השיטה נכונה, אבל איטית להחריד, כי מסלולי ההליכה מסתעפים. ברשת בגודל 100 × 100 שבה הערך בכל תא הוא סכום השורה והעמודה שלו, כל צעד ימינה או למטה הוא צעד כלפי מעלה, ומספר מסלולי ההליכה מהפינה השמאלית העליונה בלבד גדול מ-10^58. גרוע מכך, מסלול ההליכה מכל תא נתון מחושב מחדש בכל פעם שמסלול הליכה אחר עובר דרכו — ואת הבזבוז הזה הגישה הבאה מונעת.

אלגוריתם

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

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            # Each entry is one path in progress: the cell it ends on and
            # how many cells it has.
            stack = [(sr, sc, 1)]
            while stack:
                r, c, length = stack.pop()
                answer = max(answer, length)
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        stack.append((nr, nc, length + 1))
    return answer

חיפוש לעומק עם זיכרון מטמון באמצעות מחסנית משלך

האינטואיציה

נסמן את מספר התאים במסלול העולה הארוך ביותר שמתחיל בתא הזה ב-best[cell]. המסלול מסתיים שם, או שהצעד הבא שלו עובר לשכן גדול יותר וממשיך לאורך המסלול הארוך ביותר מאותו שכן. לכן best[cell] = 1 + max(best[nb]) עבור השכנים הגדולים יותר nb, או 1 אם אין כאלה. בטוח להשתמש בערך הזה שוב בגלל המבנה חסר המעגלים: התאים שלפני cell בכל מסלול קטנים יותר, ולכן הם לא יכולים להופיע אחריו, וההמשך הטוב ביותר מ-cell זהה בלי קשר לאופן שבו הגעת אליו. חשבו את best פעם אחת עבור כל תא ושמרו אותו; כך עץ ההליכות האקספוננציאלי מצטמצם לביקור אחד בכל תא.

בדוגמה הראשונה, ל-9 אין שכן גדול יותר, ולכן best שלו הוא 1. לאחר מכן הערך של 8 הוא 2, של 7 הוא 3, של 6 ושל 2 הוא 4, של 5 ושל 1 הוא 5, של 4 הוא 6, ושל 3 הוא 7 — התשובה. כל תא בודק את 4 השכנים שלו, ולכן העבודה היא O(m × n).

הקוד המתבקש הוא רקורסיבי: פונקציה שמחזירה את best עבור תא, וקוראת לעצמה עבור כל שכן גדול יותר. עומק הקריאות שלה שווה לאורך המסלול שהיא עוברת, והמגבלות מאפשרות מסלול שעובר בכל תא: ערכים שמתפתלים הלוך ושוב לרוחב רשת בגודל 100 × 100 יוצרים מסלול אחד של 10,000 תאים, בעוד ש-Python עוצרת כברירת מחדל אחרי 1,000 קריאות מקוננות. הקוד שלהלן מבצע את הרקורסיה בעצמו, ולכן שום מסלול אינו ארוך מדי עבורו. שמרו מחסנית של תאים, ובכל תא שמרו כמה מארבעת הכיוונים שלו כבר ניסיתם. בדקו את התא שבראש המחסנית: אם נותר לו כיוון, נסו אותו, ודחפו את השכן לשם אם הוא גדול יותר ועדיין לא סיימתם לעבד אותו. כשניסיתם את כל ארבעת הכיוונים, כל השכנים הגדולים יותר כבר עובדו, ולכן הסירו את התא מהמחסנית וקבעו את best שלו. זה בדיוק הסדר שבו קריאה רקורסיבית הייתה מתקדמת.

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

אלגוריתם

מלאו את best ב־0 (עדיין לא ידוע) ואת מונה הכיוונים ב־0 עבור כל תא.
עבור כל תא שערך best שלו הוא 0, דחפו אותו למחסנית.
בדקו את התא שבראש המחסנית. אם נותר בו כיוון לבדיקה, קדמו את המונה שלו ודחפו את התא השכן בכיוון הזה אם הוא נמצא בתוך הרשת, גדול יותר ולא הסתיים.
אם נוסו כל ארבעת הכיוונים, הוציאו את התא מהמחסנית והגדירו את best ל־1 ועוד ערך ה־best הגדול ביותר מבין השכנים הגדולים יותר שלו, או ל־1 אם אין לו כאלה.
החזירו את ערך ה־best הגדול ביותר.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # best[r][c]: cells on the longest increasing path that starts at (r, c).
    # 0 means not known yet.
    best = [[0] * cols for _ in range(rows)]
    # step[r][c]: how many of the 4 directions the search has tried from (r, c).
    step = [[0] * cols for _ in range(rows)]
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            if best[sr][sc]:
                continue
            # Our own stack instead of recursion: a path can be thousands of
            # cells long, past Python's limit of 1,000 nested calls.
            stack = [(sr, sc)]
            while stack:
                r, c = stack[-1]
                d = step[r][c]
                if d < 4:
                    step[r][c] = d + 1
                    nr, nc = r + dirs[d][0], c + dirs[d][1]
                    # The stack only climbs, so a larger neighbour is never on it.
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
                        stack.append((nr, nc))
                    continue
                # Every larger neighbour is finished: build on the best of them.
                stack.pop()
                length = 1
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        length = max(length, best[nr][nc] + 1)
                best[r][c] = length
                answer = max(answer, length)
    return answer

קלפו את הרשת מהפסגות שלה

האינטואיציה

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

למה: תא נמצא בשכבה k בדיוק כאשר המסלול הארוך ביותר שמתחיל בו מכיל k תאים. תא מוסר בסבב שאחרי שהשכן הגדול האחרון שלו מוסר, ולכן השכבה שלו היא 1 ועוד השכבה הגבוהה ביותר מבין שכניו הגדולים ממנו, וזוהי הנוסחה best[cell] = 1 + max(best[nb]) מהגישה הקודמת. השכבה העמוקה ביותר שייכת לתחילתו של מסלול ארוך ביותר.

בדוגמה הראשונה, הפסגה היחידה היא 9 (השכנים שלה הם 8 ו-2). הסרתה משחררת את 8, הסרת ה-8 משחררת את 7, הסרת ה-7 משחררת את 2 ואת 6, שני אלה משחררים את 1 ואת 5, ה-5 משחרר את 4, וה-4 משחרר את 3. אלה 7 שכבות, והמסלול 3, 4, 5, 6, 7, 8, 9 עולה דרך תא אחד בכל שכבה.

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

אלגוריתם

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

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
    higher = [[0] * cols for _ in range(rows)]
    layer = []
    for r in range(rows):
        for c in range(cols):
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    higher[r][c] += 1
            # A peak: no neighbour is larger, so a path from it has one cell.
            if higher[r][c] == 0:
                layer.append((r, c))
    layers = 0
    while layer:
        layers += 1
        next_layer = []
        for r, c in layer:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    higher[nr][nc] -= 1
                    # Its last larger neighbour is peeled: it is a peak now.
                    if higher[nr][nc] == 0:
                        next_layer.append((nr, nc))
        layer = next_layer
    # Each layer is one step further from a peak; the count is the longest path.
    return layers

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

הבאגים כאן נובעים מהמילה "strictly", מרקורסיה עמוקה ומהרגלים שנגררו מבעיות אחרות של רשתות.

השוואה באמצעות >= במקום >. כשיש שני ערכי 4 סמוכים, כל אחד מהם נחשב לצעד כלפי מעלה מהאחר, החצים יוצרים לולאה, חיפוש בכוח גס נע הלוך ושוב לנצח, וחיפוש עם שמירת תוצאות ביניים קורא אורך שעדיין נמצא בחישוב.
רקורסיה במסלולים ארוכים מאוד. חיפוש רקורסיבי מגיע לעומק של מספר קריאות השווה לאורך המסלול, והמגבלות מאפשרות מסלול שעובר בכל תא: ערכים שמתפתלים הלוך ושוב על פני רשת בגודל 100 × 100 יוצרים מסלול אחד של 10,000 תאים, פי עשרה ממגבלת ברירת המחדל של Python, העומדת על 1,000 קריאות מקוננות. מסלולים ארוכים כל כך דורשים חיפוש איטרטיבי עם מחסנית משלך, או הגדלה של מגבלת הרקורסיה (sys.setrecursionlimit ב-Python), וגם מגבלה גבוהה מאוד עדיין עלולה לגלוש על המחסנית הפנימית של המפרש.
דילוג על תאים שכבר בוקרו, כמו במילוי שטח. הגעה לתא שחישובו הסתיים אינה מבוי סתום: האורך השמור בו הוא בדיוק מה שהתא הנוכחי צריך. קרא אותו, אל תדלג עליו.
התחלה רק מהערך הקטן ביותר. בדוגמה הראשונה, ה-1 נותן 5 תאים, אבל התשובה, 7, מתחילה ב-3. המסלול הארוך ביותר יכול להתחיל בכל תא שאין לו שכן קטן יותר, ויכולים להיות תאים רבים כאלה.
החזרת 0. כל תא הוא מסלול באורך תא אחד, ולכן לרשת של ערכים שווים או לרשת בגודל 1 × 1 יש תשובה 1. התחל את האורך של כל תא ב-1, לא ב-0.
בגישת הקילוף, הקטנת הספירה של שכן שווה. רק שכן קטן יותר איבד שכן גדול ממנו.

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

מהי סיבוכיות הזמן של המסלול העולה הארוך ביותר במטריצה?

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

למה הבעיה הזאת אינה דורשת קבוצת ביקור?

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

האם "המסלול העולה הארוך ביותר במטריצה" הוא בעיית תכנות דינמי או בעיית גרפים?

שניהם. זהו המסלול הארוך ביותר בגרף מכוון חסר מעגלים, כלומר תכנות דינמי לפי סדר טופולוגי: התשובה לתא היא 1 ועוד התשובה הטובה ביותר מבין שכניו בעלי הערך הגדול יותר. חיפוש לעומק עם זיכרון מטמון ממלא את הטבלה לפי הסדר שבו החיפוש מסיים לעבד תאים, וקילוף טופולוגי ממלא אותה שכבה אחר שכבה, החל מהפסגות. מיון התאים מהערך הגדול ביותר לקטן ביותר נותן סדר תקף שלישי, במחיר של O(m × n × log(m × n)) עבור המיון.

במה זה שונה מתת־הסדרה העולה הארוכה ביותר?

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

Python

def longestIncreasingPath(matrix):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

צפוי

Longest Increasing Path in a Matrix

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

עקבו אחר כל מסלול עולה

חיפוש לעומק עם זיכרון מטמון באמצעות מחסנית משלך

קלפו את הרשת מהפסגות שלה

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

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

בעיות דומות