LeetCode 刷題日記
EP.05

Sliding Window
用一個視窗掃過整個陣列

#121 Best Time to Buy and Sell Stock — Sliding Window 最直觀的入門題

Joseph Chen
September 2024
Back to Blog
5 min read
1.2k views

Sliding Window 是一個把 O(n²) 的暴力雙迴圈，壓縮成 O(n) 單次遍歷的技巧。核心概念很簡單：維護一個「視窗」，根據條件動態調整它的左右邊界，不需要每次都從頭掃。Best Time to Buy and Sell Stock 是這個模式最直觀的入門題。

題目

給一個陣列 prices，prices[i] 代表第 i 天的股票價格。你只能買賣一次，求最大獲利。

Input / Output
Input:  prices = [10, 1, 5, 6, 7, 1]
Output: 6
# 第 2 天買（price=1），第 5 天賣（price=7）→ 獲利 7-1=6

Input:  prices = [10, 8, 7, 5, 2]
Output: 0
# 一路跌，無論如何都獲利不了 → 回傳 0

暴力解：兩層迴圈 O(n²)

最直覺的做法：枚舉所有買入和賣出的組合。

暴力解 — O(n²)
def maxProfit(prices):
    max_profit = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            profit = prices[j] - prices[i]
            max_profit = max(max_profit, profit)
    return max_profit
⏱ Time: O(n²)💾 Space: O(1)

這樣做會超時（LeetCode 會 TLE）。問題在於：每次移動買入點，賣出點都要從頭掃。但我們根本不需要這樣——賣出的最佳時機，就是在「當前買入點之後的最高價」，而這可以用一次遍歷追蹤。

Sliding Window 思維

用兩個指針：min_price（目前最低買入價）和當前遍歷到的價格。

規則很簡單：

→遇到更低的價格，更新 min_price（視窗左邊界往右移）
→否則計算當前獲利，更新最大值
prices = [10, 1, 5, 6, 7, 1]
daypriceminprofitmax
0101000
111↓00
25144↑
36155↑
47166↑
511↓06

解法

Sliding Window — O(n)
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]
        profit = 0

        for price in prices:
            if price < min_price:
                min_price = price          # 遇到更低價，更新買入點
            else:
                profit = max(profit, price - min_price)  # 計算當前獲利

        return profit
⏱ Time: O(n)💾 Space: O(1)
✅ 這是你的 GitHub 上的解法。用 min 作為變數名的版本是一樣的邏輯，只是 min 是 Python 內建函式，建議改用 min_price 避免覆蓋內建名稱。

Sliding Window 的通用模板

Buy and Sell Stock 是「固定視窗右端，動態更新左端」的變形。更通用的 Sliding Window 是動態調整視窗大小的版本，適用於「最長/最短子字串」類型的題目：

通用 Sliding Window 模板
def sliding_window(s):
    window = {}      # 視窗內的狀態（通常是 dict 或計數器）
    left = 0
    result = 0

    for right in range(len(s)):
        # 1. 把 s[right] 加入視窗
        window[s[right]] = window.get(s[right], 0) + 1

        # 2. 當視窗不符合條件，縮小左邊界
        while window_is_invalid(window):
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1

        # 3. 更新結果（視窗大小 = right - left + 1）
        result = max(result, right - left + 1)

    return result

Longest Substring Without Repeating Characters

視窗內不能有重複字元，遇到重複就縮小左邊

Minimum Window Substring

視窗內要包含所有目標字元，滿足條件後縮小左邊找最短

Longest Repeating Character Replacement

視窗內替換次數不超過 k，超過就縮小左邊

Sliding Window 的精髓：右邊界推進「擴大」視窗，左邊界推進「縮小」視窗。整個過程，left 和 right 都只往右走，總共最多走 2n 步，所以是 O(n)。

本篇重點整理

🪟Sliding Window = 動態視窗，right 擴大，left 縮小
📈Buy and Sell Stock：追蹤當前最低買入點，同時計算獲利
⚠️別用 min 當變數名，會覆蓋 Python 內建函式
🔄通用模板：right 每次推進一格，left 在違反條件時縮進

上一篇

EP.04 — Two Pointers

從 "0P" 踩坑說起

下一篇

EP.06 — Stack

Valid Parentheses 與單調棧

LeetCode
Sliding Window
Array
Python
EP.05