問題 1047: 隣接する重複文字の完全除去

問題定義

英小文字のみで構成される文字列が引数として渡されます。この文字列に対して、「隣接する同一文字をペアで取り除く」という演算を繰り返し適用します。すべての演算が行き詰まった時点で残っている文字列を返却してください。解答は一意に決まります。

• 入力例: "abbaca" → 出力: "ca"
• 制約条件: 文字列長は [1, 20000] の範囲内で、英小文字のみを含む。

解決策とアルゴリズム

本問題は、文字列を一方向に走査しながら「直前に保留していた文字」との比較を繰り返すことで解決できます。効率的な実装のために、動的確保した配列をスタックとして利用します。

1. メモリ確保と初期化: 最大でも元の文字列長を超えることはありませんため、strlen + 1 の領域を確保します。最後にNULL終端文字を追加する必要があるため、1バイト余裕を持たせます。
2. 一方向走査と状態遷移: インデックスを前方に進めながら各文字を処理します。現在着目している文字が、スタックの直上要素（最後の追加文字）と等しい場合、それは「隣接する重複」であるためスタックポップ（トップインデックスを1減算）を実行します。異なる場合、あるいはスタックが空の場合はプッシュ（トップインデックスに加算し、データを格納）します。
3. 結果成型: 走査完了後、末尾に '\0' を挿入することでC言語互換の文字列化を終了させ、ポインタを返却します。

実装コード

/* LeetCode 1047: Remove All Adjacent Duplicates In String */
char* removeDuplicates(char* input_str) {
    int str_len = strlen(input_str);
    /* 最大長分＋NULL終端分の確保 */
    char* result_buf = (char*)malloc(sizeof(char) * (str_len + 1));
    int buf_ptr = 0; /* スタックのトップインデックス */

    for (int idx = 0; input_str[idx] != '\0'; ++idx) {
        /* 既に要素が存在し、かつ直前の要素と一致する場合 → ポップ */
        if (buf_ptr > 0 && result_buf[buf_ptr - 1] == input_str[idx]) {
            buf_ptr--;
        } else {
            /* 一致しないか空の場合 → プッシュ */
            result_buf[buf_ptr++] = input_str[idx];
        }
    }
    /* 文字列終端を追加して有効なC文字列にする */
    result_buf[buf_ptr] = '\0';
    return result_buf;
}

問題 239: スライディングウィンドウの最大値検索

問題定義

整数配列 nums と正の整数 k が与えられます。幅 k の固定ウィンドウが配列の左端から右端へ一歩ずつ移動します。各位置において、ウィンドウ内に含まれる要素の最大値を抽出した配列を返してください。

• 入力例1: nums = [1,3,-1,-3,5,3,6,7], k = 3 → 出力: [3,3,5,5,6,7]
• 制約条件: 配列長 [1, 10^5], 要素値 [-10^4, 10^4], 1 ≤ k ≤ nums.length

解決策とアルゴリズム

単純な暴力探索は O(N×K) の計算量になり、大きな入力ではタイムアウトします。O(N) で動作させるには、各ウィンドウの移動伴随に「候補となる最大値」を保持する単調递减キュー（Monotonic Queue）を活用するのが定石です。

1. キューの役割: キューには配列の添字を格納します。キューは作成時から末尾に向かって要素値が減少するように保たれます。これにより、キューの先頭要素は必ず現在のウィンドウ内の最大値を指し示します。
2. 単調性の維持: 新しい要素がウィンドウに入った際、その値よりも小さい要素は二度と最大値候補になることがありません。そのため、末尾から自分以上の要素がある限り連続して破棄（tail--）し、その後自身の添字を末尾に追加します。
3. ウィンドウの推移管理: ウィンドウが完全なサイズ k に達したら、キュー先頭の値を結果リストに登録します。次にウィンドウを右にずらす際、もしキュー先頭の添字がウィンドウの左枠を超えている場合（＝該当の最大値が対象外になった）、キュー先頭を削除（head++）します。

実装コード

/* LeetCode 239: Sliding Window Maximum */
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    int total_elements = numsSize;
    
    /* 境界チェック */
    if (total_elements == 0 || k == 0) {
        *returnSize = 0;
        return NULL;
    }

    int result_capacity = total_elements - k + 1;
    int* result_arr = (int*)malloc(sizeof(int) * result_capacity);
    *returnSize = result_capacity;

    /* 単調キュー用バッファとポインタ */
    int* mono_queue = (int*)malloc(sizeof(int) * total_elements);
    int q_head = 0, q_tail = -1;
    int write_idx = 0;

    for (int win_right = 0; win_right < total_elements; ++win_right) {
        /* 単調递减性質の強制：現在値より小さい末尾要素をすべて除去 */
        while (q_tail >= q_head && nums[win_right] > nums[mono_queue[q_tail]]) {
            q_tail--;
        }
        /* 現在の添字をキュー尾部に登録 */
        mono_queue[++q_tail] = win_right;

        /* ウィンドウがサイズ k に到達した地点で記録 */
        if (win_right >= k - 1) {
            /* キュー先頭が現在ウィンドウの最大値 */
            result_arr[write_idx++] = nums[mono_queue[q_head]];

            /* ウィンドウを右へシフトする準備：先頭要素が窓の左端を外れる場合、キューから除外 */
            if (mono_queue[q_head] == win_right - k + 1) {
                q_head++;
            }
        }
    }

    free(mono_queue); /* 作業用キューのメモリ解放 */
    return result_arr;
}