LeetCode 239. スライディングウィンドウ最大値 問題リンク：239. スライディングウィンドウ最大値 - LeetCode

​アプローチ：

ウィンドウの左端が常に最大値となるように維持し、popleft操作で自動的に最大値を取得できるようにする。

# Pythonで双端キューを使用した実装
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k == 0:
            return []
        window_queue = deque()
        for i in range(k):
            while window_queue and window_queue[-1] < nums[i]:
                window_queue.pop()
            window_queue.append(nums[i])
        result = [window_queue[0]]
        for i in range(k, len(nums)):
            if window_queue[0] == nums[i - k]:
                window_queue.popleft()
            while window_queue and window_queue[-1] < nums[i]:
                window_queue.pop()
            window_queue.append(nums[i])
            result.append(window_queue[0])
        return result

# Javaでの実装例
import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0 || k > nums.length) {
            return new int[0];
        }

        Deque<Integer> indexQueue = new LinkedList<>();
        int[] output = new int[nums.length - k + 1];
        int outputIndex = 0;

        for (int i = 0; i < nums.length; i++) {
            // ウィンドウ外のインデックスを削除
            while (!indexQueue.isEmpty() && indexQueue.peekFirst() <= i - k) {
                indexQueue.pollFirst();
            }

            // 現在の要素よりも小さい値をキューから除去
            while (!indexQueue.isEmpty() && nums[indexQueue.peekLast()] <= nums[i]) {
                indexQueue.pollLast();
            }

            // 現在のインデックスをキューに追加
            indexQueue.offerLast(i);

            // ウィンドウサイズがkに達したら最大値を記録
            if (i >= k - 1) {
                output[outputIndex++] = nums[indexQueue.peekFirst()];
            }
        }

        return output;
    }
}

実装上のポイント：

キューの先頭が現在のウィンドウ範囲内であるかを確認する際、i - k + 1ではなくi - kの比較を用いる点が注意が必要。

LeetCode 347. 上位K頻度要素

問題リンク：347. 上位K頻度要素 - LeetCode

​ アプローチ：

頻度順に要素を並べる際、ハッシュマップとヒープを組み合わせて効率的に処理する。

コード：

# Pythonによるヒープ使用例
import heapq
from collections import defaultdict

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # フレキシビリティを高めるためdefaultdictを使用
        freq_map = defaultdict(int)
        for num in nums:
            freq_map[num] += 1
        
        # サイズkの最小ヒープを構築
        min_heap = []
        
        # 頻度情報をヒープに挿入
        for num, count in freq_map.items():
            heapq.heappush(min_heap, (count, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        
        # 結果リストへの変換
        return [num for count, num in min_heap]

# Javaでの実装例
import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // フレキシビリティを高めるためMapを使用
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // サイズkの最大ヒープを構築
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(k, (a, b) -> b[0] - a[0]);

        // 頻度情報をヒープに挿入
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            maxHeap.offer(new int[]{entry.getValue(), entry.getKey()});
        }

        // 結果リストへの変換
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll()[1];
        }
        return result;
    }
}

実装上のポイント：

Pythonでは最小ヒープを用いてk要素を保持し、Javaでは最大ヒープで頻度順に抽出するという異なるアプローチを取っている。