DSA Interview Prep · Pelajaran

Maksimum Tetingkap Gelongsor dengan Dek Monoton

Kekalkan dek indeks menurun untuk menjawab pertanyaan maksimum dalam tetingkap dalam O(1) bagi setiap unsur, lalu menyelesaikan masalah maksimum tetingkap gelongsor dalam O(n).

Pelajaran 3 daripada 413 langkah

Maksimum Tetingkap Gelongsor dengan Dek Monoton ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Masalah Nilai Maksimum Tetingkap Gelongsor

Masalah Nilai Maksimum Tetingkap Gelongsor (LeetCode 239) memberikan suatu tatasusunan dan saiz tetingkap k. Apabila tetingkap bergerak dari kiri ke kanan satu kedudukan pada satu masa, hasilkan elemen maksimum dalam setiap tetingkap. Pendekatan daya kasar mengira maksimum bagi setiap tetingkap yang mengandungi k elemen dalam O(k), lalu memberikan jumlah keseluruhan O(nk), yang terlalu perlahan untuk k yang besar.

Penyelesaian menggunakan baris gilir dua hujung monotonik mencapai O(n) secara keseluruhan dengan mengekalkan baris gilir menurun yang menyimpan indeks. Bahagian hadapan sentiasa menyimpan indeks elemen maksimum tetingkap semasa, lalu memberikan query maksimum O(1) sambil membenarkan operasi pada kedua-dua hujung.

from collections import deque

# Brute force O(nk) for comparison
def sliding_max_brute(nums, k):
    return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print('Input:', nums, 'k=', k)
print('Expected: [3, 3, 5, 5, 6, 7]')
print('Brute:   ', sliding_max_brute(nums, k))

Baris Gilir Dua Hujung Monotonik: Idea Utama

Kekalkan baris gilir dua hujung menurun monotonik yang menyimpan indeks (bukan nilai). Invariannya ialah: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Sebelum menambahkan indeks i:

Buang indeks yang luput dari bahagian hadapan: jika deque[0] <= i - k, indeks itu telah keluar dari tetingkap.
Buang indeks dengan nilai lebih kecil dari bahagian belakang: selagi nums[deque[-1]] <= nums[i], indeks tersebut tidak mungkin menjadi maksimum bagi mana-mana tetingkap akan datang (indeks itu berada di sebelah kiri dan nilainya lebih kecil), jadi buangkannya.

Selepas operasi ini, masukkan i ke bahagian belakang. Bahagian hadapan sentiasa memberikan maksimum tetingkap semasa.

from collections import deque

def sliding_window_max(nums, k):
    dq = deque()  # stores indices; values are decreasing
    result = []

    for i, n in enumerate(nums):
        # 1. Remove indices outside the current window
        while dq and dq[0] <= i - k:
            dq.popleft()

        # 2. Remove indices with smaller values from the back
        while dq and nums[dq[-1]] <= n:
            dq.pop()

        dq.append(i)

        # 3. Record max when first full window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])   # front = max of current window

    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3))  # [3, 3, 5, 5, 6, 7]

Menjejak Baris Gilir Dua Hujung Langkah demi Langkah

Mari kita jejaki [1, 3, -1, -3, 5, 3, 6, 7] dengan k=3:

i=0 (1): dq=[0]
i=1 (3): pop 0 (1<3), dq=[1]
i=2 (-1): -1<3, jadi kekalkan, dq=[1,2]. Tetingkap [1,3,-1], maksimum=nums[1]=3
i=3 (-3): -3<-1, dq=[1,2,3]. Semak bahagian hadapan: 1 > 3-3=0, OK. Maksimum tetingkap=3
i=4 (5): pop 3,2,1 (semuanya lebih kecil), dq=[4]. Bahagian hadapan 4 > 4-3=1, OK. Maksimum=5
i=5 (3): 3<5, dq=[4,5]. Bahagian hadapan 4 > 5-3=2, OK. Maksimum=5
i=6 (6): pop 5,4 (kedua-duanya lebih kecil), dq=[6]. Maksimum=6
i=7 (7): pop 6, dq=[7]. Maksimum=7

from collections import deque

def sliding_window_max_trace(nums, k):
    dq = deque()
    result = []
    for i, n in enumerate(nums):
        while dq and dq[0] <= i - k:
            print(f'  Remove expired index {dq[0]} from front')
            dq.popleft()
        while dq and nums[dq[-1]] <= n:
            print(f'  Remove smaller index {dq[-1]} (val={nums[dq[-1]]}) from back')
            dq.pop()
        dq.append(i)
        print(f'i={i} n={n}: dq={list(dq)} vals={[nums[j] for j in dq]}')
        if i >= k - 1:
            win_max = nums[dq[0]]
            result.append(win_max)
            print(f'  Window {nums[max(0,i-k+1):i+1]} -> max={win_max}')
    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
result = sliding_window_max_trace(nums, 3)
print('Result:', result)

Mengapa Setiap Elemen Dimasukkan dan Dikeluarkan Paling Banyak Sekali

Jaminan O(n) datang daripada hujah teramortisasi yang sama seperti tindanan monotonik: setiap indeks ditambahkan ke baris gilir dua hujung tepat sekali dan dikeluarkan paling banyak sekali, sama ada dari bahagian hadapan apabila luput atau dari bahagian belakang apabila digantikan. Jumlah operasi baris gilir dua hujung sepanjang seluruh gelung adalah paling banyak 2n.

Gelung dalaman tidak meningkatkan kerumitan keseluruhan — sebarang pengeluaran yang dilakukan dalam gelung tersebut dibayar oleh operasi penambahan sebelumnya. Penaakulan ini sama seperti bagi tindanan monotonik, tetapi diperluas kepada baris gilir dua hujung yang membenarkan pengeluaran dari kedua-dua hujung.

from collections import deque

def sliding_window_max_instrumented(nums, k):
    dq = deque()
    result = []
    front_pops = back_pops = pushes = 0

    for i, n in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft(); front_pops += 1
        while dq and nums[dq[-1]] <= n:
            dq.pop(); back_pops += 1
        dq.append(i); pushes += 1
        if i >= k - 1:
            result.append(nums[dq[0]])

    print(f'n={len(nums)}: pushes={pushes}, front_pops={front_pops}, back_pops={back_pops}')
    print(f'Total deque ops = {pushes + front_pops + back_pops} <= 3n = {3*len(nums)}')
    return result

import random; random.seed(0)
nums = [random.randint(-100, 100) for _ in range(20)]
sliding_window_max_instrumented(nums, 5)

Minimum Tetingkap Gelongsor

Minimum tetingkap gelongsor ialah pasangan simetri bagi masalah maksimum: kekalkan baris gilir dua hujung menaik monotonik (lakukan pop dari bahagian belakang apabila elemen baharu lebih kecil daripada elemen di belakang). Bahagian hadapan sentiasa menyimpan minimum tetingkap semasa. Semua langkah lain sama seperti versi maksimum — cuma terbalikkan arah perbandingan.

Masalah yang meminta minimum tetingkap gelongsor sering muncul sebagai submasalah dalam algoritma yang lebih besar. Sebagai contoh, kos minimum untuk menggerakkan barang sepanjang laluan dengan k hentian perantaraan mungkin memerlukan minimum tetingkap gelongsor pada tatasusunan DP.

from collections import deque

def sliding_window_min(nums, k):
    dq = deque()  # increasing monotonic deque
    result = []

    for i, n in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()               # expired
        while dq and nums[dq[-1]] >= n:
            dq.pop()                   # pop larger values from back
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])  # front = min
    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print('Max k=3:', sliding_window_min.__name__, '->', end=' ')
print(sliding_window_min(nums, 3))   # [-1, -3, -3, -3, 3, 3]

from collections import deque
def sliding_window_max(nums, k):
    dq = deque(); result = []
    for i, n in enumerate(nums):
        while dq and dq[0] <= i-k: dq.popleft()
        while dq and nums[dq[-1]] <= n: dq.pop()
        dq.append(i)
        if i >= k-1: result.append(nums[dq[0]])
    return result

print('Max k=3:', sliding_window_max(nums, 3))   # [3,3,5,5,6,7]

Permainan Lompatan VI: DP dengan Baris Gilir Dua Hujung Monotonik

Permainan Lompatan VI (LeetCode 1696) ialah contoh klasik yang menggabungkan DP dan baris gilir dua hujung monotonik. Diberi suatu tatasusunan dan saiz lompatan maksimum k, bermula pada indeks 0, pada setiap langkah anda melompat 1 hingga k langkah ke hadapan sambil menambahkan skor sel sasaran. Maksimumkan jumlah skor. Pengulangan DP ialah dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). Nilai maksimum tetingkap gelongsor pada tatasusunan DP memberikan jumlah keseluruhan O(n).

from collections import deque

def max_result(nums, k):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])   # indices of max dp values in current window

    for i in range(1, n):
        # Remove expired indices
        while dq and dq[0] < i - k:
            dq.popleft()
        # dp[i] = nums[i] + max dp in window [i-k, i-1]
        dp[i] = nums[i] + dp[dq[0]]
        # Maintain decreasing deque on dp values
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)

    return dp[n - 1]

print(max_result([1,-1,-2,4,-7,3], 2))    # 7: path 1->4->3
print(max_result([10,-5,-2,4,0,3], 3))    # 17: path 10->4->3
print(max_result([1,-5,-20,4,-1,3,-6,-3], 2))  # 0

Nilai Maksimum Tetingkap Gelongsor: Alternatif Pepohon Segmen

Bagi masalah yang saiz tetingkapnya berubah-ubah (bukan k tetap), baris gilir dua hujung monotonik tidak boleh digunakan secara langsung. Sebaliknya, gunakan jadual jarang untuk query maksimum julat statik dalam O(1) bagi setiap query selepas prapemprosesan O(n log n), atau pepohon segmen untuk kemas kini dinamik dengan O(log n) bagi setiap query. Walau bagaimanapun, bagi tetingkap gelongsor dengan k tetap, baris gilir dua hujung tiada tandingan pada O(n).

Dalam temu duga, sentiasa utamakan baris gilir dua hujung monotonik O(n) berbanding pepohon segmen O(n log n) apabila saiz tetingkap adalah malar. Nyatakan pertukaran yang terlibat: baris gilir dua hujung tidak dapat menangani saiz tetingkap sewenang-wenangnya atau kemas kini, manakala pepohon segmen boleh berbuat demikian.

# Sparse table for static RMQ (range maximum query)
import math

def build_sparse_table(arr):
    n = len(arr)
    LOG = int(math.log2(n)) + 1 if n else 1
    table = [[0]*n for _ in range(LOG)]
    table[0] = arr[:]
    j = 1
    while (1 << j) <= n:
        for i in range(n - (1 << j) + 1):
            table[j][i] = max(table[j-1][i], table[j-1][i + (1 << (j-1))])
        j += 1
    return table

def query(table, l, r):
    k = int(math.log2(r - l + 1))
    return max(table[k][l], table[k][r - (1 << k) + 1])

arr = [1, 3, -1, -3, 5, 3, 6, 7]
table = build_sparse_table(arr)
k = 3
result = [query(table, i, i + k - 1) for i in range(len(arr) - k + 1)]
print('Sparse table result:', result)  # [3, 3, 5, 5, 6, 7]

Subtatasusunan Terpanjang bagi Satu Selepas Memadam Satu Elemen

LeetCode 1493: diberikan tatasusunan binari, cari panjang subtatasusunan 1 yang terpanjang selepas memadam tepat satu elemen (yang boleh berupa 0 atau 1). Ini ialah masalah tetingkap gelongsor. Kekalkan tetingkap dengan paling banyak satu 0. Apabila tetingkap mempunyai lebih daripada satu 0, kecilkan tetingkap dari sebelah kiri.

Ini menggunakan corak tetingkap gelongsor bersaiz berubah-ubah — bukan baris gilir dua hujung. Walau bagaimanapun, jika digabungkan dengan teknik tetingkap maksimum: selepas mencari semua tetingkap yang sah, panjang maksimum ialah jawapannya. Maksud 'padam satu elemen' ialah kita membenarkan tepat satu 0 dalam tetingkap 1 kita.

def longest_subarray(nums):
    left = 0
    zeros = 0
    max_len = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > 1:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        # Window [left, right] has at most 1 zero
        # After deleting one element, length = right - left (not +1, since we delete one)
        max_len = max(max_len, right - left)

    return max_len

print(longest_subarray([1,1,0,1]))       # 3: delete the 0
print(longest_subarray([0,1,1,1,0,1,1,0,1]))  # 5
print(longest_subarray([1,1,1]))          # 2: must delete one 1

Perbandingan Baris Gilir Dua Hujung, Baris Gilir dan Tindanan

Memahami masa untuk menggunakan setiap bekas adalah penting dalam temu duga:

Tindanan (senarai): LIFO, akses pada satu hujung. Gunakan untuk DFS, penghuraian ungkapan dan masalah tindanan monotonik.
Baris Gilir (baris gilir dua hujung dengan appendleft/popleft): FIFO, kemasukan pada satu hujung dan pop pada hujung yang satu lagi. Gunakan untuk BFS dan penjadualan tugasan.
Baris Gilir Dua Hujung: kedua-dua hujung boleh diakses dalam O(1). Gunakan untuk tetingkap gelongsor dengan luput (buang dari hadapan) dan invarian monotonik (buang dari belakang). Nilai maksimum tetingkap gelongsor ialah masalah baris gilir dua hujung yang lazim.

collections.deque Python ialah alat untuk ketiga-tiga kegunaan ini. Gunakan append/pop untuk kelakuan tindanan dan append/popleft atau appendleft/pop untuk kelakuan baris gilir atau baris gilir dua hujung.

from collections import deque

# deque as stack
stack = deque()
stack.append(1); stack.append(2); stack.append(3)
print('Stack pop:', stack.pop())  # 3 (LIFO)

# deque as queue
queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print('Queue pop:', queue.popleft())  # 1 (FIFO)

# deque as sliding window with front expiry + back monotonic
dq = deque()
nums = [3, 1, 4, 1, 5, 9, 2, 6]
k = 3
for i, n in enumerate(nums):
    while dq and dq[0] <= i - k: dq.popleft()   # expire front
    while dq and nums[dq[-1]] <= n: dq.pop()     # maintain back
    dq.append(i)
    if i >= k - 1:
        print(f'Window {nums[max(0,i-k+1):i+1]}: max={nums[dq[0]]}')

Subtatasusunan Terpendek dengan Jumlah Sekurang-kurangnya K: Baris Gilir Dua Hujung + Jumlah Awalan

Subtatasusunan Terpendek dengan Jumlah Sekurang-kurangnya K (LeetCode 862) ialah masalah lanjutan yang menggabungkan jumlah awalan dengan baris gilir dua hujung monotonik. Bina jumlah awalan, kemudian gunakan baris gilir dua hujung untuk mencari, bagi setiap titik hujung kanan, jumlah awalan paling kiri yang memenuhi prefix[right] - prefix[left] >= k. Baris gilir dua hujung itu mengekalkan jumlah awalan menaik (lakukan pop dari belakang untuk mengekalkan susunan menaik), dan melakukan pop dari hadapan untuk mengumpulkan jawapan yang sah.

Ini ialah salah satu masalah tetingkap gelongsor yang paling sukar kerana ia melibatkan nombor negatif (menyebabkan kaedah dua penuding mudah tidak boleh digunakan) dan memerlukan baris gilir dua hujung berfungsi sebagai struktur monotonik serta mekanisme luput.

from collections import deque

def shortest_subarray(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    dq = deque()    # monotonic increasing deque of indices into prefix
    result = float('inf')

    for right in range(n + 1):
        # Pop from front: valid subarrays ending at `right`
        while dq and prefix[right] - prefix[dq[0]] >= k:
            result = min(result, right - dq.popleft())
        # Pop from back: maintain increasing deque
        while dq and prefix[dq[-1]] >= prefix[right]:
            dq.pop()
        dq.append(right)

    return result if result != float('inf') else -1

print(shortest_subarray([1], 1))               # 1
print(shortest_subarray([1, 2], 4))            # -1
print(shortest_subarray([2, -1, 2], 3))        # 3
print(shortest_subarray([84,-37,32,40,95], 167))  # 3

Strategi Temu Duga untuk Masalah Baris Gilir Dua Hujung

Kenal pasti masalah baris gilir dua hujung monotonik melalui petunjuk berikut: (1) anda memerlukan maksimum atau minimum bagi tetingkap gelongsor bersaiz tetap, (2) anda memerlukan pengulangan DP dp[i] = f(nums[i], max(dp[i-k..i-1])), atau (3) anda memerlukan indeks sah terdekat yang memenuhi syarat monotonik.

Dalam temu duga, tulis penyelesaian baris gilir dua hujung dengan kemas: import deque, kekalkan dua invarian (luput di hadapan, monotonisiti di belakang), dan pulangkan hasil bermula pada indeks k-1. Sentiasa nyatakan kerumitan masa O(n) dan ruang O(k) untuk baris gilir dua hujung (paling banyak k indeks disimpan serentak), serta bandingkan dengan pendekatan daya kasar O(nk) untuk menunjukkan penambahbaikannya.

from collections import deque

# Clean, interview-ready template
def sliding_window_max_template(nums, k):
    if not nums or k == 0:
        return []

    dq = deque()   # monotonic decreasing, stores indices
    result = []

    for i in range(len(nums)):
        # Invariant 1: remove expired indices (outside window)
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Invariant 2: remove indices with smaller values (useless)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Record result once first full window is established
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Complexity: O(n) time, O(k) space
print(sliding_window_max_template([1,3,-1,-3,5,3,6,7], 3))
print(sliding_window_max_template([1], 1))
print(sliding_window_max_template([], 3))

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Ulang Kaji Pelajaran

Dalam pelajaran ini, anda telah mempelajari bahawa: baris gilir dua hujung menurun monotonik mengekalkan maksimum tetingkap pada bahagian hadapannya sambil membuang dari bahagian belakang elemen yang lebih kecil daripada elemen baharu, indeks yang luput dibuang dari bahagian hadapan apabila berada di luar sempadan tetingkap, dan setiap indeks dimasukkan serta dikeluarkan paling banyak sekali, lalu memberikan jumlah keseluruhan O(n) dengan ruang baris gilir dua hujung O(k). Seterusnya, kita akan menyelesaikan masalah memerangkap air hujan menggunakan tindanan monotonik dan pendekatan dua penuding.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 30
Pelajaran: 120

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Maksimum Tetingkap Gelongsor dengan Dek Monoton” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Maksimum Tetingkap Gelongsor dengan Dek Monoton”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Maksimum Tetingkap Gelongsor dengan Dek Monoton”?

Kekalkan dek indeks menurun untuk menjawab pertanyaan maksimum dalam tetingkap dalam O(1) bagi setiap unsur, lalu menyelesaikan masalah maksimum tetingkap gelongsor dalam O(n). Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.

Berapa lamakah pelajaran “Maksimum Tetingkap Gelongsor dengan Dek Monoton” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Tindanan Monoton: Menaik berbanding Menurun
Segi Empat Terbesar dalam Histogram
Maksimum Tetingkap Gelongsor dengan Dek Monoton
Memerangkap Air Hujan: Tindanan dan Dua Penuding

← Kembali ke DSA Interview Prep