Kas yra slenkantis langų metodas (sliding-window technique)?

Question

IT Interview Practice · Accepted Answer

**Slenkantis langų** metodas palaiko tiesią eilutę (langą) virš masyvo arba eilutės ir jį slenka, o ne perskaičiuoja iš naujo, sprendžiant daugelį submasyvo/poeilutės uždavinių per **O(n)**.

## Idėja

Platinkite langą, perkeldami dešinįjį kraštą; susitraukite jį, perkeldami kairįjį kraštą, kai pažeidžiama sąlyga. Iš naujo naudokite ankstesnį skaičiavimą, o ne peržiūrėkite iš naujo.

## Pavyzdys: didžiausia bet kurio k dydžio lango suma

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Sudėtingumas

- **Laikas:** O(n) — kiekvienas elementas į langą ir iš jo išeina po vieną kartą.
- **Vieta:** O(1) fiksuotiems langams, O(k), kai sekate turinį.

## Kada naudoti / spąstai

Naudokite "ilgiausio/trumpiausio/maksimalaus submasyvo su savybe X" uždaviniams. **Kintamiems** langams, perkelkite kairįjį žymeklį, kad atkurtumėte sąlygą. Saugokitės off-by-one klaidų, kai pridedate/šalinate ribinius elementus.

## Kodėl tai svarbu

Slenkantis langas elimina nereikalingą darbą, O(n·k) perskaičiavimą paverčiant vienu praėjimu.

Tai yra pagrindinis modelis poeilučių ir submasyvo uždaviniams, kurie nuolat pasirodo interviu.

Idėja — iš naujo panaudoti ankstesnį rezultatą, o ne jį perskaičiuoti — yra universali ir taikoma srautiniams bei realaus laiko duomenims.

Idėja

Pavyzdys: didžiausia bet kurio k dydžio lango suma

Sudėtingumas

Kada naudoti / spąstai

Kodėl tai svarbu

Susiję klausimai