LeetCode Hot 100 (51-80)

title51 - 岛屿数量

NumberOfIslands.java

package leecode100.title51;

/**
 * 题目：岛屿数量
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * 此外，你可以假设该网格的四条边均被水包围。
 *
 * 示例 1：
 * 输入：grid = [
 *   ["1","1","1","1","0"],
 *   ["1","1","0","1","0"],
 *   ["1","1","0","0","0"],
 *   ["0","0","0","0","0"]
 * ]
 * 输出：1
 *
 * 示例 2：
 * 输入：grid = [
 *   ["1","1","0","0","0"],
 *   ["1","1","0","0","0"],
 *   ["0","0","1","0","0"],
 *   ["0","0","0","1","1"]
 * ]
 * 输出：3
 */
public class NumberOfIslands {
    /**
     * 解题思路：
     * 1. 遍历整个网格。
     * 2. 当遇到 '1' 时，岛屿数量加 1，并以此为起点进行深度优先搜索 (DFS)。
     * 3. 在 DFS 过程中，将所有相连的 '1' 标记为 '0'（或其它标记），以避免重复计数。
     * 4. 最终返回岛屿的总数。
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int numIslands = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    numIslands++;
                    dfs(grid, r, c);
                }
            }
        }

        return numIslands;
    }

    private void dfs(char[][] grid, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0'; // 标记为已访问
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public static void main(String[] args) {
        NumberOfIslands solution = new NumberOfIslands();
        char[][] grid1 = {
            {'1', '1', '1', '1', '0'},
            {'1', '1', '0', '1', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '0', '0', '0'}
        };
        System.out.println("Example 1: " + solution.numIslands(grid1)); // Output: 1

        char[][] grid2 = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        };
        System.out.println("Example 2: " + solution.numIslands(grid2)); // Output: 3
    }
}

title52 - 腐烂的橘子

RottingOranges.java

package leecode100.title52;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目：腐烂的橘子
 * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，腐烂的橘子 周围 4 个方向上相邻的新鲜橘子都会腐烂。
 * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
 *
 * 示例 1：
 * 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
 * 输出：4
 */
public class RottingOranges {
    /**
     * 解题思路：
     * 1. 使用广度优先搜索 (BFS)。
     * 2. 首先将所有腐烂的橘子 (2) 的坐标加入队列，并统计新鲜橘子 (1) 的总数。
     * 3. 每一层 BFS 代表一分钟，将队列中腐烂橘子四周的新鲜橘子变腐烂，并加入队列。
     * 4. 记录经过的分钟数。
     * 5. 最后检查是否还有新鲜橘子。
     */
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.offer(new int[]{r, c});
                } else if (grid[r][c] == 1) {
                    freshCount++;
                }
            }
        }

        if (freshCount == 0) return 0;

        int minutes = 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean rottedAny = false;
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                for (int[] dir : directions) {
                    int nr = curr[0] + dir[0];
                    int nc = curr[1] + dir[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        queue.offer(new int[]{nr, nc});
                        freshCount--;
                        rottedAny = true;
                    }
                }
            }
            if (rottedAny) minutes++;
        }

        return freshCount == 0 ? minutes : -1;
    }

    public static void main(String[] args) {
        RottingOranges solution = new RottingOranges();
        int[][] grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
        System.out.println("Minutes: " + solution.orangesRotting(grid)); // Output: 4
    }
}

title53 - 课程表

CourseSchedule.java

package leecode100.title53;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 题目：课程表
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
 * 给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 *
 * 示例 1：
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：true
 */
public class CourseSchedule {
    /**
     * 解题思路：
     * 1. 这是一个拓扑排序问题，判断有向图中是否存在环。
     * 2. 使用入度数组记录每门课的先修课程数量。
     * 3. 使用邻接表存储图。
     * 4. 将所有入度为 0 的课程加入队列。
     * 5. 依次从队列中取出课程，将其指向的后续课程入度减 1。如果后续课程入度变为 0，则加入队列。
     * 6. 最后检查学习过的课程数量是否等于总课程数。
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] pre : prerequisites) {
            inDegree[pre[0]]++;
            adj.get(pre[1]).add(pre[0]);
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            count++;
            for (int next : adj.get(curr)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return count == numCourses;
    }

    public static void main(String[] args) {
        CourseSchedule solution = new CourseSchedule();
        int[][] pre = {{1, 0}};
        System.out.println("Can finish: " + solution.canFinish(2, pre)); // Output: true
    }
}

title54 - 实现 Trie (前缀树)

ImplementTriePrefixTree.java

package leecode100.title54;

/**
 * 题目：实现 Trie (前缀树)
 * Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。
 * 这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
 * 请你实现 Trie 类：
 * Trie() 初始化前缀树对象。
 * void insert(String word) 向前缀树中插入字符串 word 。
 * boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
 * boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
 * 
 * 示例 1：
 * 输入
 * ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
 * [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
 * 输出
 * [null, null, true, false, true, null, true]
 * 
 * 解释
 * Trie trie = new Trie();
 * trie.insert("apple");
 * trie.search("apple");   // 返回 True
 * trie.search("app");     // 返回 False
 * trie.startsWith("app"); // 返回 True
 * trie.insert("app");
 * trie.search("app");     // 返回 True
 * 
 * 提示：
 * 1 <= word.length, prefix.length <= 2000
 * word 和 prefix 仅由小写英文字母组成
 * insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次
 */
public class ImplementTriePrefixTree {
    /**
     * 解题思路：
     * 三个核心操作
     *
     * 插入单词 (insert)
     * 从根节点开始，逐个字符遍历
     * 字符不存在就新建节点，存在就继续往下走
     * 单词结尾节点标记 isEnd = true
     *
     * 查找单词 (search)
     * 先找到单词前缀对应的节点
     * 检查该节点是否存在且是单词结尾(isEnd为true)
     *
     * 查找前缀 (startsWith)
     * 只需要找到前缀对应的节点即可
     * 只要节点存在就说明前缀存在
     */

    static class Trie {
        Trie[] children;
        boolean isEnd;
        
        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
                /**
                 * 代码解析
                 * node: 当前遍历到的树节点
                 * node.children: 当前节点的子节点数组或列表
                 * index: 用于定位特定子节点的索引
                 * node.children[index]: 获取当前节点的第 index 个子节点
                 * 整体含义: 将当前节点移动到指定的子节点
                 */
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            return node != null && node.isEnd;
        }

        public boolean startsWith(String prefix) {
            return searchPrefix(prefix) != null;
        }

        private Trie searchPrefix(String prefix) {
            Trie node = this;
            for (char c : prefix.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    return null;
                }
                node = node.children[index];
            }
            return node;
        }
    }

    public static void main(String[] args) {
        // Test case from example
        ImplementTriePrefixTree implementTrie = new ImplementTriePrefixTree();
        Trie trie = new Trie();
        
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // return True
        System.out.println(trie.search("app"));     // return False
        System.out.println(trie.startsWith("app")); // return True
        
        trie.insert("app");
        System.out.println(trie.search("app"));     // return True
    }
}

title55 - 全排列

Permutations.java

package leecode100.title55;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class Permutations {
    /**
     * 解题思路：
     * 1. 使用回溯算法。
     * 2. 维护一个 used 数组记录哪些数字已经被使用。
     * 3. 递归地选择未使用的数字加入当前路径。
     * 4. 当路径长度等于数组长度时，将路径加入结果集。
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, path, res);
        return res;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                path.add(nums[i]);
                backtrack(nums, used, path, res);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Permutations solution = new Permutations();
        int[] nums = {1, 2, 3};
        System.out.println(solution.permute(nums));
    }
}

title56 - 子集

Subsets.java

package leecode100.title56;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 */
public class Subsets {
    /**
     * 解题思路：
     * 1. 使用回溯算法。
     * 2. 每次递归都将当前路径加入结果集（因为每个节点都是一个子集）。
     * 3. 从当前索引开始向后遍历，选择元素加入路径并递归。
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, nums, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(i + 1, nums, path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Subsets solution = new Subsets();
        int[] nums = {1, 2, 3};
        System.out.println(solution.subsets(nums));
    }
}

title57 - 电话号码的字母组合

LetterCombinationsOfAPhoneNumber.java

package leecode100.title57;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 示例 1：
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 */
public class LetterCombinationsOfAPhoneNumber {
    private String[] map = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) return res;
        backtrack(0, digits, new StringBuilder(), res);
        return res;
    }

    private void backtrack(int index, String digits, StringBuilder sb, List<String> res) {
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }

        String letters = map[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            sb.append(c);
            backtrack(index + 1, digits, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        LetterCombinationsOfAPhoneNumber solution = new LetterCombinationsOfAPhoneNumber();
        System.out.println(solution.letterCombinations("23"));
    }
}

title58 - 组合总和

CombinationSum.java

package leecode100.title58;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：组合总和
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
 * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。
 *
 * 示例 1：
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 */
public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, candidates, target, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int start, int[] candidates, int target, List<Integer> path, List<List<Integer>> res) {
        if (target < 0) return;
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            // 因为可以重复使用，所以传 i 而不是 i + 1
            backtrack(i, candidates, target - candidates[i], path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum solution = new CombinationSum();
        int[] candidates = {2, 3, 6, 7};
        System.out.println(solution.combinationSum(candidates, 7));
    }
}

title59 - 括号生成

GenerateParentheses.java

package leecode100.title59;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 */
public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(0, 0, n, new StringBuilder(), res);
        return res;
    }

    private void backtrack(int left, int right, int n, StringBuilder sb, List<String> res) {
        if (sb.length() == n * 2) {
            res.add(sb.toString());
            return;
        }

        if (left < n) {
            sb.append('(');
            backtrack(left + 1, right, n, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right < left) {
            sb.append(')');
            backtrack(left, right + 1, n, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        GenerateParentheses solution = new GenerateParentheses();
        System.out.println(solution.generateParenthesis(3));
    }
}

title60 - 单词搜索

WordSearch.java

package leecode100.title60;

/**
 * 题目：单词搜索
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
 * 如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 *
 * 示例 1：
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 */
public class WordSearch {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, word, 0, i, j, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int r, int c, boolean[][] visited) {
        if (index == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length 
            || visited[r][c] || board[r][c] != word.charAt(index)) {
            return false;
        }

        visited[r][c] = true;
        boolean res = dfs(board, word, index + 1, r - 1, c, visited)
                   || dfs(board, word, index + 1, r + 1, c, visited)
                   || dfs(board, word, index + 1, r, c - 1, visited)
                   || dfs(board, word, index + 1, r, c + 1, visited);
        visited[r][c] = false;
        return res;
    }

    public static void main(String[] args) {
        WordSearch solution = new WordSearch();
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        System.out.println(solution.exist(board, "ABCCED")); // true
    }
}

title61 - 分割回文串

PalindromePartitioning.java

package leecode100.title61;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * 回文串 是正着读和反着读都一样的字符串。
 * 
 * 示例 1：
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 
 * 示例 2：
 * 输入：s = "a"
 * 输出：[["a"]]
 * 
 * 提示：
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 */
public class PalindromePartitioning {
    /**
     * 解题思路：
     * 1. 使用回溯算法
     * 2. 从字符串的起始位置开始，尝试所有可能的分割点
     * 3. 如果当前分割出的子串是回文串，则递归处理剩余部分
     * 4. 当处理到字符串末尾时，将当前分割方案加入结果集
     */

    public static void main(String[] args) {
        PalindromePartitioning solution = new PalindromePartitioning();
        String s1 = "aab";
        List<List<String>> result1 = solution.partition(s1);
        System.out.println("Test case 1 result: " + result1);

        String s2 = "a";
        List<List<String>> result2 = solution.partition(s2);
        System.out.println("Test case 2 result: " + result2);
    }

    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                path.add(s.substring(start, i + 1));
                backtrack(s, i + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

title62 - N 皇后

NQueens.java

package leecode100.title62;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 题目：N 皇后
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * 
 * 示例 1：
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 
 * 示例 2：
 * 输入：n = 1
 * 输出：[["Q"]]
 * 
 * 提示：
 * 1 <= n <= 9
 */
public class NQueens {
    /**
     * 解题思路：
     * 1. 使用回溯算法，逐行放置皇后
     * 2. 对于每一行，尝试在每一列放置皇后
     * 3. 放置前检查当前位置是否合法（同列、左上方、右上方是否有皇后）
     * 4. 如果合法，则放置皇后并递归处理下一行
     * 5. 找到一个解后，将棋盘状态转换为要求的格式并存入结果集
     */

    public static void main(String[] args) {
        NQueens solution = new NQueens();
        int n1 = 4;
        List<List<String>> result1 = solution.solveNQueens(n1);
        System.out.println("Test case 1 (n=4) solutions count: " + result1.size());
        for (List<String> sol : result1) {
            System.out.println(sol);
        }

        int n2 = 1;
        List<List<String>> result2 = solution.solveNQueens(n2);
        System.out.println("Test case 2 (n=1) result: " + result2);
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtrack(board, 0, res);
        return res;
    }

    private void backtrack(char[][] board, int row, List<List<String>> res) {
        if (row == board.length) {
            res.add(construct(board));
            return;
        }

        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1, res);
                board[row][col] = '.';
            }
        }
    }

    private boolean isValid(char[][] board, int row, int col) {
        // 检查列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 检查左上方
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上方
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }

    private List<String> construct(char[][] board) {
        List<String> path = new ArrayList<>();
        for (char[] row : board) {
            path.add(new String(row));
        }
        return path;
    }
}

title63 - 搜索插入位置

SearchInsertPosition.java

package leecode100.title63;

/**
 * 题目：搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
 * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * 
 * 示例 1:
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 * 
 * 示例 2:
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 * 
 * 示例 3:
 * 输入: nums = [1,3,5,6], target = 7
 * 输出: 4
 * 
 * 提示:
 * 1 <= nums.length <= 10^4
 * -10^4 <= nums[i] <= 10^4
 * nums 为 无重复元素 的 升序 排列数组
 * -10^4 <= target <= 10^4
 */
public class SearchInsertPosition {
    /**
     * 解题思路：
     * 1. 标准的二分查找
     * 2. 如果找到目标值，直接返回索引
     * 3. 如果没找到，最后 left 指针所在的位置就是插入位置
     */

    public static void main(String[] args) {
        SearchInsertPosition solution = new SearchInsertPosition();
        int[] nums = {1,3,5,6};
        System.out.println("Test case 1 (target=5): " + solution.searchInsert(nums, 5)); // 2
        System.out.println("Test case 2 (target=2): " + solution.searchInsert(nums, 2)); // 1
        System.out.println("Test case 3 (target=7): " + solution.searchInsert(nums, 7)); // 4
    }

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

title64 - 搜索二维矩阵

SearchA2DMatrix.java

package leecode100.title64;

/**
 * 题目：搜索二维矩阵
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 
 * 示例 1：
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 * 
 * 示例 2：
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 * 
 * 提示：
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 100
 * -10^4 <= matrix[i][j], target <= 10^4
 */
public class SearchA2DMatrix {
    /**
     * 解题思路：
     * 1. 由于矩阵的特性，可以将二维矩阵看作一个一维有序数组
     * 2. 使用二分查找
     * 3. 关键在于一维索引与二维坐标的转换：
     *    row = index / n
     *    col = index % n
     */

    public static void main(String[] args) {
        SearchA2DMatrix solution = new SearchA2DMatrix();
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        System.out.println("Test case 1 (target=3): " + solution.searchMatrix(matrix, 3)); // true
        System.out.println("Test case 2 (target=13): " + solution.searchMatrix(matrix, 13)); // false
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = matrix[mid / n][mid % n];
            if (val == target) {
                return true;
            } else if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

title65 - 在排序数组中查找元素的第一个和最后一个位置

FindFirstAndLastPositionOfElementInSortedArray.java

package leecode100.title65;

import java.util.Arrays;

/**
 * 题目：在排序数组中查找元素的第一个和最后一个位置
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
 * 请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 * 
 * 示例 1：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 
 * 示例 2：
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 */
public class FindFirstAndLastPositionOfElementInSortedArray {
    /**
     * 解题思路：
     * 1. 使用两次二分查找
     * 2. 第一次查找第一个大于等于 target 的位置（左边界）
     * 3. 第二次查找第一个大于 target 的位置，减 1 即为右边界
     */

    public static void main(String[] args) {
        FindFirstAndLastPositionOfElementInSortedArray solution = new FindFirstAndLastPositionOfElementInSortedArray();
        int[] nums = {5,7,7,8,8,10};
        System.out.println("Test case 1 (target=8): " + Arrays.toString(solution.searchRange(nums, 8))); // [3, 4]
        System.out.println("Test case 2 (target=6): " + Arrays.toString(solution.searchRange(nums, 6))); // [-1, -1]
    }

    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    private int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

title66 - 搜索旋转排序数组

SearchInRotatedSortedArray.java

package leecode100.title66;

/**
 * 题目：搜索旋转排序数组
 * 整数数组 nums 按升序排列，数组中的值 互不相同 。
 * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转。
 * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 * 
 * 示例 1：
 * 输入：nums = [4,5,6,7,0,1,2], target = 0
 * 输出：4
 */
public class SearchInRotatedSortedArray {
    /**
     * 解题思路：
     * 1. 二分查找
     * 2. 关键在于：旋转后的数组，mid 将数组分成两部分，其中一部分必定是有序的
     * 3. 判断哪一部分有序，然后判断 target 是否在有序部分内
     */

    public static void main(String[] args) {
        SearchInRotatedSortedArray solution = new SearchInRotatedSortedArray();
        int[] nums = {4,5,6,7,0,1,2};
        System.out.println("Test case 1 (target=0): " + solution.search(nums, 0)); // 4
    }

    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) { // 左边有序
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else { // 右边有序
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

title67 - 寻找旋转排序数组中的最小值

FindMinimumInRotatedSortedArray.java

package leecode100.title67;

/**
 * 题目：寻找旋转排序数组中的最小值
 * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。
 * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。
 * 请你找出并返回数组中的 最小元素 。
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 * 
 * 示例 1：
 * 输入：nums = [3,4,5,1,2]
 * 输出：1
 */
public class FindMinimumInRotatedSortedArray {
    /**
     * 解题思路：
     * 1. 二分查找
     * 2. 比较 nums[mid] 和 nums[right]
     * 3. 如果 nums[mid] < nums[right]，说明最小值在左侧（包含 mid）
     * 4. 如果 nums[mid] > nums[right]，说明最小值在右侧（不包含 mid）
     */

    public static void main(String[] args) {
        FindMinimumInRotatedSortedArray solution = new FindMinimumInRotatedSortedArray();
        int[] nums = {3,4,5,1,2};
        System.out.println("Minimum: " + solution.findMin(nums)); // 1
    }

    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
}

title68 - 寻找两个正序数组的中位数

MedianOfTwoSortedArrays.java

package leecode100.title68;

/**
 * 题目：寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * 请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * 
 * 示例 1：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 
 * 示例 2：
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 */
public class MedianOfTwoSortedArrays {
    /**
     * 解题思路：
     * 1. 寻找第 k 小的数
     * 2. 每次比较两个数组中第 k/2 个元素，排除较小的那一部分
     * 3. 递归处理，直到 k=1 或其中一个数组为空
     */

    public static void main(String[] args) {
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();
        int[] nums1 = {1,3}, nums2 = {2};
        System.out.println("Median: " + solution.findMedianSortedArrays(nums1, nums2)); // 2.0
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + 
                getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        } else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }
}

title69 - 有效的括号

ValidParentheses.java

package leecode100.title69;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 题目：有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 * 
 * 示例 1：
 * 输入：s = "()"
 * 输出：true
 */
public class ValidParentheses {
    /**
     * 解题思路：
     * 1. 使用栈
     * 2. 遇到左括号入栈
     * 3. 遇到右括号，检查栈顶是否匹配
     */

    public static void main(String[] args) {
        ValidParentheses solution = new ValidParentheses();
        System.out.println("Is valid: " + solution.isValid("()[]{}")); // true
    }

    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) return false;
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

title70 - 最小栈

MinStack.java

package leecode100.title70;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 题目：最小栈
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * 实现 MinStack 类:
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素。
 * 
 * 示例 1:
 * 输入：
 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
 * [[],[-2],[0],[-3],[],[],[],[]]
 * 输出：
 * [null,null,null,null,-3,null,0,-2]
 */
public class MinStack {
    /**
     * 解题思路：
     * 1. 使用辅助栈存储最小值
     * 2. 辅助栈与主栈同步操作，辅助栈顶始终是当前主栈中的最小值
     */
    private Deque<Integer> xStack;
    private Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        xStack.push(val);
        minStack.push(Math.min(minStack.peek(), val));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println("Min: " + minStack.getMin()); // -3
        minStack.pop();
        System.out.println("Top: " + minStack.top());    // 0
        System.out.println("Min: " + minStack.getMin()); // -2
    }
}

title71 - 字符串解码

DecodeString.java

package leecode100.title71;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 题目：字符串解码
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。
 * 注意 k 保证为正整数。
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，
 * 且输入的方括号总是符合格式要求的。
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，
 * 例如不会出现像 3a 或 2[4] 的输入。
 * 
 * 示例 1:
 * 输入: s = "3[a]2[bc]"
 * 输出: "aaabcbc"
 * 
 * 示例 2:
 * 输入: s = "3[a2[c]]"
 * 输出: "accaccacc"
 * 
 * 示例 3:
 * 输入: s = "2[abc]3[cd]ef"
 * 输出: "abcabccdcdcdef"
 * 
 * 示例 4:
 * 输入: s = "abc3[cd]xyz"
 * 输出: "abccdcdcdxyz"
 * 
 * 提示:
 * 1 <= s.length <= 30
 * s 由小写英文字母、数字和方括号 '[]' 组成
 * s 保证是一个有效的输入
 * s 中所有整数的取值范围为 [1, 300]
 */
public class DecodeString {
    /**
     * 解题思路：
     * 1. 使用两个栈分别存储数字和字符串
     * 2. 遇到数字时，解析完整的数字（可能多位）
     * 3. 遇到'['时，将当前数字和字符串入栈，并重置
     * 4. 遇到']'时，从栈中取出数字和字符串，进行重复操作
     * 5. 遇到普通字符时，直接添加到当前字符串中
     */

    public static void main(String[] args) {
        // Test case 1
        DecodeString solution = new DecodeString();
        String s1 = "3[a]2[bc]";
        String result1 = solution.decodeString(s1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        String s2 = "3[a2[c]]";
        String result2 = solution.decodeString(s2);
        System.out.println("Test case 2 result: " + result2);

        // Test case 3
        String s3 = "2[abc]3[cd]ef";
        String result3 = solution.decodeString(s3);
        System.out.println("Test case 3 result: " + result3);

        // Test case 4
        String s4 = "abc3[cd]xyz";
        String result4 = solution.decodeString(s4);
        System.out.println("Test case 4 result: " + result4);
    }

    public String decodeString(String s) {
        Deque<Integer> cntStack = new ArrayDeque<>();
        Deque<StringBuilder> strStack = new ArrayDeque<>();

        strStack.push(new StringBuilder());
        int num = 0;

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            } else if (ch == '[') {
                cntStack.push(num);
                strStack.push(new StringBuilder());
                num = 0;
            } else if (ch == ']') {
                int cnt = cntStack.pop();
                String str = strStack.pop().toString();
                StringBuilder current = strStack.peek();
                while (cnt-- > 0) {
                    current.append(str);
                }
            } else {
                strStack.peek().append(ch);
            }
        }

        return strStack.peek().toString();
    }
}

title72 - 每日温度

DailyTemperatures.java

package leecode100.title72;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 题目：每日温度
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
 * 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * 
 * 示例 1:
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 
 * 示例 2:
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 * 
 * 示例 3:
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 * 
 * 提示:
 * 1 <= temperatures.length <= 10^5
 * 30 <= temperatures[i] <= 100
 */
public class DailyTemperatures {
    /**
     * 解题思路：
     * 1. 单调栈问题
     * 2. 使用单调递减栈来存储温度的索引
     * 3. 遍历温度数组，当当前温度大于栈顶索引对应的温度时，
     *    说明找到了栈顶索引的下一个更高温度
     * 4. 计算天数差并更新结果数组
     * 5. 将当前索引入栈，继续处理
     */

    public static void main(String[] args) {
        // Test case 1
        DailyTemperatures solution = new DailyTemperatures();
        int[] temperatures1 = {73,74,75,71,69,72,76,73};
        int[] result1 = solution.dailyTemperatures(temperatures1);
        System.out.println("Test case 1 result: " + Arrays.toString(result1));

        // Test case 2
        int[] temperatures2 = {30,40,50,60};
        int[] result2 = solution.dailyTemperatures(temperatures2);
        System.out.println("Test case 2 result: " + Arrays.toString(result2));

        // Test case 3
        int[] temperatures3 = {30,60,90};
        int[] result3 = solution.dailyTemperatures(temperatures3);
        System.out.println("Test case 3 result: " + Arrays.toString(result3));
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[length];

        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int preIndex = stack.pop();
                res[preIndex] = i - preIndex;
            }
            stack.push(i);
        }

        return res;
    }
}

title73 - 柱状图中最大的矩形

LargestRectangleInHistogram.java

package leecode100.title73;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 题目：柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 
 * 示例 1:
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 
 * 示例 2:
 * 输入：heights = [2,4]
 * 输出：4
 * 
 * 提示:
 * 1 <= heights.length <= 10^5
 * 0 <= heights[i] <= 10^4
 */
public class LargestRectangleInHistogram {
    /**
     * 解题思路：
     * 1. 单调栈问题
     * 2. 对于每个柱子，我们需要找到它左边和右边第一个比它矮的柱子
     * 3. 使用单调递增栈来处理
     * 4. 当遇到一个比栈顶元素矮的柱子时，说明找到了栈顶元素右边第一个较矮的柱子
     * 5. 此时可以计算以栈顶元素为高度的矩形面积
     * 6. 矩形的宽度是右边较矮柱子与左边较矮柱子之间的距离
     */

    public static void main(String[] args) {
        // Test case 1
        LargestRectangleInHistogram solution = new LargestRectangleInHistogram();
        int[] heights1 = {2,1,5,6,2,3};
        int result1 = solution.largestRectangleArea(heights1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] heights2 = {2,4};
        int result2 = solution.largestRectangleArea(heights2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];   // left[i]表示柱子i左边第一个比它矮的柱子索引
        int[] right = new int[n];  // right[i]表示柱子i右边第一个比它矮的柱子索引
        Arrays.fill(right, n);
        
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 确定每个柱子左边第一个较矮的柱子
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                // 当前柱子是栈顶元素右边第一个较矮的柱子
                right[stack.pop()] = i;
            }
            // 栈顶元素就是当前柱子左边第一个较矮的柱子
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        // 计算最大面积
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            // 面积 = 高度 * 宽度
            // 宽度 = 右边较矮柱子索引 - 左边较矮柱子索引 - 1
            int area = heights[i] * (right[i] - left[i] - 1);
            maxArea = Math.max(maxArea, area);
        }
        
        return maxArea;
    }
}

title74 - 数组中第K个最大元素

KthLargestElementInAnArray.java

package leecode100.title74;

/**
 * 题目：数组中第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 * 
 * 示例 1:
 * 输入: [3,2,1,5,6,4], k = 2
 * 输出: 5
 * 
 * 示例 2:
 * 输入: [3,2,3,1,2,4,5,5,6], k = 4
 * 输出: 4
 * 
 * 提示：
 * 1 <= k <= nums.length <= 10^5
 * -10^4 <= nums[i] <= 10^4
 */
public class KthLargestElementInAnArray {
    /**
     * 解题思路：
     * 1. 使用堆排序的思想解决这个问题
     * 2. 构建一个最大堆
     * 3. 执行k-1次堆排序操作，每次将堆顶最大元素移到末尾
     * 4. 第k次操作后，堆顶元素就是第k大的元素
     * 5. buildMaxHeap方法用于构建初始的最大堆
     * 6. maxHeapify方法用于维护堆的性质
     */

    public static void main(String[] args) {
        // Test case 1
        KthLargestElementInAnArray solution = new KthLargestElementInAnArray();
        int[] nums1 = {3,2,1,5,6,4};
        int k1 = 2;
        int result1 = solution.findKthLargest(nums1, k1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {3,2,3,1,2,4,5,5,6};
        int k2 = 4;
        int result2 = solution.findKthLargest(nums2, k2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        // 构建最大堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, i, len);
        }
        // 执行k-1次
        int cnt = k-1;
        int end = nums.length - 1;

        while ( cnt-- > 0 ) {
            swap(nums, 0, end);     // 将最大元素移到末尾
            len--;
            maxHeapify(nums, 0, len);  // 重新调整堆
            end--;
        }
        return nums[0];  // 堆顶即为第K大元素
    }

    private void maxHeapify(int[] nums, int i, int len) {
        int l = i * 2 + 1;    // 左子节点
        int r = i * 2 + 2;    // 右子节点
        int largest = i;      // 假设当前节点最大

        if (l < len && nums[l] > nums[largest]) {
            largest = l;
        }
        if (r < len && nums[r] > nums[largest]) {
            largest = r;
        }

        if (largest != i) {
            swap(nums, i, largest);
            maxHeapify(nums, largest, len);
        }
    }

    private void swap(int[] nums, int i, int largest) {
        int temp = nums[i];
        nums[i] = nums[largest];
        nums[largest] = temp;
    }
}

title75 - 前K个高频元素

TopKFrequentElements.java

package leecode100.title75;

import java.util.*;

/**
 * 题目：前K个高频元素
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
 * 你可以按 任意顺序 返回答案。
 * 
 * 示例 1:
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 
 * 示例 2:
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * 
 * 提示：
 * 1 <= nums.length <= 10^5
 * k 的取值范围是 [1, 数组中不相同的元素的个数]
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 * 
 * 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 */
public class TopKFrequentElements {
    /**
     * 解题思路：
     * 1. 首先使用HashMap统计每个元素的频率
     * 2. 将元素和频率的对应关系存储在List中
     * 3. 使用堆排序的思想，构建最大堆（按频率排序）
     * 4. 执行k次堆排序操作，每次获取频率最高的元素
     * 5. 将获取的元素存储在结果数组中
     */

    public static void main(String[] args) {
        // Test case 1
        TopKFrequentElements solution = new TopKFrequentElements();
        int[] nums1 = {1,1,1,2,2,3};
        int k1 = 2;
        int[] result1 = solution.topKFrequent(nums1, k1);
        System.out.println("Test case 1 result: " + Arrays.toString(result1));

        // Test case 2
        int[] nums2 = {1};
        int k2 = 1;
        int[] result2 = solution.topKFrequent(nums2, k2);
        System.out.println("Test case 2 result: " + Arrays.toString(result2));
    }

    public int[] topKFrequent(int[] nums, int k) {
        // 统计频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(map.entrySet());

        // 构建最大堆（按频率排序）
        buildMaxHeap(entries, entries.size());

        int[] res = new int[k];
        int end = entries.size() - 1;
        for (int i = 0; i < k; i++) {
            // 获取频率最高的元素
            res[i] = entries.get(0).getKey();
            // 交换并调整堆
            swap(entries, 0, end);
            maxHeapify(entries, 0, end);
            end--;
        }

        return res;
    }

    private void buildMaxHeap(List<Map.Entry<Integer, Integer>> entries, int size) {
        for (int i = size / 2 - 1; i >= 0; i--) {
            maxHeapify(entries, i, size);
        }
    }

    private void maxHeapify(List<Map.Entry<Integer, Integer>> entries, int i, int size) {
        int l = i * 2 + 1;
        int r = i * 2 + 2;
        int largest = i;
        if (l < size && entries.get(l).getValue() > entries.get(largest).getValue()) {
            largest = l;
        }
        if (r < size && entries.get(r).getValue() > entries.get(largest).getValue()) {
            largest = r;
        }
        if (largest != i) {
            swap(entries, i, largest);
            maxHeapify(entries, largest, size);
        }
    }

    private void swap(List<Map.Entry<Integer, Integer>> entries, int i, int largest) {
        Map.Entry<Integer, Integer> temp = entries.get(i);
        entries.set(i, entries.get(largest));
        entries.set(largest, temp);
    }
}

title76 - 数据流的中位数

FindMedianFromDataStream.java

package leecode100.title76;

import java.util.PriorityQueue;

/**
 * 题目：数据流的中位数
 * 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
 * 例如：
 * [2,3,4] 的中位数是 3
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 * 设计一个支持以下两种操作的数据结构：
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 * 
 * 示例 1：
 * 输入：
 * ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
 * [[],[1],[2],[],[3],[]]
 * 输出：[null,null,null,1.50000,null,2.00000]
 * 
 * 示例 2：
 * 输入：
 * ["MedianFinder","addNum","findMedian","addNum","findMedian"]
 * [[],[2],[],[3],[]]
 * 输出：[null,null,2.00000,null,2.50000]
 * 
 * 提示：
 * 最多会对 addNum、findMedian 进行 50000 次调用。
 */
public class FindMedianFromDataStream {
    /**
     * 解题思路：
     * 1. 使用两个堆来维护数据流的中位数
     * 2. 一个最大堆存储较小的一半元素，一个最小堆存储较大的一半元素
     * 3. 保持两个堆的大小平衡，最大堆的大小等于最小堆的大小或比最小堆大1
     * 4. 添加元素时，根据元素大小决定放入哪个堆，并调整堆的平衡
     * 5. 查找中位数时，如果两个堆大小相等，返回两个堆顶元素的平均值；
     *    如果最大堆比最小堆大1，返回最大堆的堆顶元素
     */

    public static void main(String[] args) {
        // Test case 1
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.printf("Median after adding 1,2: %.5f%n", medianFinder.findMedian()); // 1.50000
        medianFinder.addNum(3);
        System.out.printf("Median after adding 3: %.5f%n", medianFinder.findMedian()); // 2.00000
    }

    static class MedianFinder {
        private PriorityQueue<Integer> minHeap; // 存储较大的一半元素（最小堆）
        private PriorityQueue<Integer> maxHeap; // 存储较小的一半元素（最大堆）

        public MedianFinder() {
            minHeap = new PriorityQueue<>(); // 最小堆
            maxHeap = new PriorityQueue<>((x, y) -> y - x); // 最大堆
        }

        public void addNum(int num) {
            if (minHeap.isEmpty() || num > minHeap.peek()) {
                minHeap.offer(num);
            } else {
                maxHeap.offer(num);
            }

            // 平衡两个堆的大小
            if (minHeap.size() > maxHeap.size() + 1) {
                maxHeap.offer(minHeap.poll());
            } else if (maxHeap.size() > minHeap.size()) {
                minHeap.offer(maxHeap.poll());
            }
        }

        public double findMedian() {
            if (minHeap.size() == maxHeap.size()) {
                // 两个堆大小相等，返回两个堆顶元素的平均值
                return minHeap.peek() * 0.5 + maxHeap.peek() * 0.5;
            } else {
                // 最小堆比最大堆多一个元素，返回最小堆的堆顶元素
                return minHeap.peek();
            }
        }
    }
}

title77 - 买卖股票的最佳时机

BestTimeToBuyAndSellStock.java

package leecode100.title77;

/**
 * 题目：买卖股票的最佳时机
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
 * 设计一个算法来计算你所能获取的最大利润。
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 * 
 * 示例 1:
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 * 
 * 示例 2:
 * 输入: [7,6,4,3,1]
 * 输出: 0
 * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 * 
 * 提示:
 * 1 <= prices.length <= 10^5
 * 0 <= prices[i] <= 10^4
 */
public class BestTimeToBuyAndSellStock {
    /*
     * 解题思路：
     * 1. 遍历价格数组，记录到目前为止的最低价格
     * 2. 对于每一天，计算当天卖出能获得的最大利润（当天价格 - 最低价格）
     * 3. 更新全局最大利润
     * 4. 时间复杂度 O(n)，空间复杂度 O(1)
     */

    public static void main(String[] args) {
        // Test case 1
        BestTimeToBuyAndSellStock solution = new BestTimeToBuyAndSellStock();
        int[] prices1 = {7,1,5,3,6,4};
        int result1 = solution.maxProfit(prices1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] prices2 = {7,6,4,3,1};
        int result2 = solution.maxProfit(prices2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int from = 0;
        int maxProfit = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (prices[i] < prices[from]) {
                from = i;
            }
            maxProfit = Math.max(maxProfit, prices[i] - prices[from]);
        }

        return Math.max(maxProfit, 0);
    }
}

title78 - 跳跃游戏

JumpGame.java

package leecode100.title78;

/**
 * 题目：跳跃游戏
 * 给定一个非负整数数组 nums ，你最初位于数组的第一个下标。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标。
 * 
 * 示例 1:
 * 输入: nums = [2,3,1,1,4]
 * 输出: true
 * 解释: 可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
 * 
 * 示例 2:
 * 输入: nums = [3,2,1,0,4]
 * 输出: false
 * 解释: 无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ，所以永远不可能到达最后一个下标。
 * 
 * 提示:
 * 1 <= nums.length <= 10^4
 * 0 <= nums[i] <= 10^5
 */
public class JumpGame {
    /**
     * 解题思路：
     * 1. 使用贪心算法解决这个问题
     * 2. 维护一个变量maxReach表示当前能到达的最远下标
     * 3. 遍历数组，对于每个位置i：
     *    - 如果i > maxReach，说明无法到达位置i，返回false
     *    - 更新maxReach为max(maxReach, i + nums[i])
     *    - 如果maxReach >= nums.length - 1，说明可以到达最后一个下标，返回true
     * 4. 遍历完成后返回true
     */

    public static void main(String[] args) {
        // Test case 1
        JumpGame solution = new JumpGame();
        int[] nums1 = {2,3,1,1,4};
        boolean result1 = solution.canJump(nums1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {3,2,1,0,4};
        boolean result2 = solution.canJump(nums2);
        System.out.println("Test case 2 result: " + result2);
    }

    public boolean canJump(int[] nums) {
        int maxReach = 0; // 当前能到达的最远下标
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false; // 已经跳不到这里
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) return true; // 直接提前返回
        }
        return true;
    }
}

title79 - 跳跃游戏 II

JumpGameII.java

package leecode100.title79;

/**
 * 题目：跳跃游戏 II
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置。
 * 
 * 示例 1:
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 * 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 * 
 * 示例 2:
 * 输入: nums = [2,3,0,1,4]
 * 输出: 2
 * 
 * 提示:
 * 1 <= nums.length <= 10^4
 * 0 <= nums[i] <= 1000
 */
public class JumpGameII {
    /**
     * 解题思路：
     * 1. 使用贪心算法解决这个问题
     * 2. 维护三个变量：
     *    - end: 当前跳跃范围的边界
     *    - maxPosition: 在当前跳跃范围内能到达的最远位置
     *    - steps: 跳跃次数
     * 3. 遍历数组（除最后一个元素外），对于每个位置i：
     *    - 更新maxPosition为max(maxPosition, i + nums[i])
     *    - 如果i == end，说明需要进行下一次跳跃：
     *      * 更新end为maxPosition
     *      * 增加steps
     * 4. 返回steps
     */

    public static void main(String[] args) {
        // Test case 1
        JumpGameII solution = new JumpGameII();
        int[] nums1 = {2,3,1,1,4};
        int result1 = solution.jump(nums1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        int[] nums2 = {2,3,0,1,4};
        int result2 = solution.jump(nums2);
        System.out.println("Test case 2 result: " + result2);
    }

    public int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, nums[i] + i);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }

        return steps;
    }
}

title80 - 划分字母区间

PartitionLabels.java

package leecode100.title80;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：划分字母区间
 * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，
 * 同一字母最多出现在一个片段中。结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 S 。
 * 返回一个表示每个字符串片段的长度的列表。
 * 
 * 示例 1:
 * 输入: s = "ababcbacadefegdehijhklij"
 * 输出: [9,7,8]
 * 解释: 划分结果为 "ababcbaca", "defegde", "hijhklij"。
 * 
 * 示例 2:
 * 输入: s = "eccbbbbdec"
 * 输出: [10]
 * 
 * 提示:
 * 1 <= s.length <= 500
 * s 仅由小写英文字母组成
 */
public class PartitionLabels {
    /**
     * 解题思路：
     * 1. 首先遍历字符串，记录每个字符最后出现的位置
     * 2. 再次遍历字符串，维护当前片段的结束位置maxEnd
     * 3. 对于每个字符，更新maxEnd为max(maxEnd, 该字符最后出现的位置)
     * 4. 当当前位置i等于maxEnd时，说明当前片段结束，记录长度并更新下一个片段的起始位置
     * 5. 时间复杂度O(n)，空间复杂度O(1)
     */

    public static void main(String[] args) {
        // Test case 1
        PartitionLabels solution = new PartitionLabels();
        String s1 = "ababcbacadefegdehijhklij";
        List<Integer> result1 = solution.partitionLabels(s1);
        System.out.println("Test case 1 result: " + result1);

        // Test case 2
        String s2 = "eccbbbbdec";
        List<Integer> result2 = solution.partitionLabels(s2);
        System.out.println("Test case 2 result: " + result2);
    }

    public List<Integer> partitionLabels(String s) {
       int[] last = new int[26];
       int n = s.length();
        for (int i = 0; i < n; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int maxEnd = 0;
        int start = 0;
        for (int i = 0; i < n; i++) {
            maxEnd = Math.max(maxEnd, last[s.charAt(i) - 'a']);
            if (i == maxEnd) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }

        return res;
    }
}