class Solution {
    public int numIslands(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        // ans：岛屿数量
        int ans = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    // 新岛屿起点：计数后淹没整片连通陆地
                    ans++;
                    dfs(grid, i, j, rows, cols);
                }
            }
        }
        return ans;
    }

    // 从 (i, j) 出发，把上下左右相连的陆地全部改为 '0'
    private void dfs(char[][] grid, int i, int j, int rows, int cols) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0'; // 标记已访问（原地修改）
        dfs(grid, i - 1, j, rows, cols);
        dfs(grid, i + 1, j, rows, cols);
        dfs(grid, i, j - 1, rows, cols);
        dfs(grid, i, j + 1, rows, cols);
    }
}

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // freshCount：剩余新鲜橘子数量
        int freshCount = 0;
        // queue：当前已腐烂、可向外扩散的格子
        Queue<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    freshCount++;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        if (freshCount == 0) {
            return 0;
        }

        // directions：上下左右四向
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int minutes = 0;

        // 还有新鲜橘子且仍能扩散时继续按「分钟」分层 BFS
        while (!queue.isEmpty() && freshCount > 0) {
            minutes++;
            int size = queue.size(); // 本分钟的腐烂源数量
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] dir : directions) {
                    int nr = cur[0] + dir[0];
                    int nc = cur[1] + dir[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; // 感染
                        freshCount--;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }

        // ans：全部腐烂所需分钟；若仍有新鲜则不可能
        int ans = (freshCount == 0) ? minutes : -1;
        return ans;
    }
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // adj：邻接表，adj[u] 为以 u 为先修的后继课程列表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        // indegree[c]：课程 c 尚需满足的先修数量
        int[] indegree = new int[numCourses];

        for (int[] pre : prerequisites) {
            int course = pre[0];
            int preCourse = pre[1];
            indegree[course]++;
            adj.get(preCourse).add(course); // preCourse → course
        }

        // 入度为 0：无先修，可立即学习
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int finished = 0; // 已修完的课程数
        while (!queue.isEmpty()) {
            int course = queue.poll();
            finished++;
            for (int next : adj.get(course)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // ans：能否修完全部课程（拓扑序列长度是否为 n）
        boolean ans = (finished == numCourses);
        return ans;
    }
}

class Trie {
    private class TrieNode {
        boolean isEnd;           // 是否有单词在此结束
        TrieNode[] children;     // children[c-'a']：下一字符对应子结点

        TrieNode() {
            isEnd = false;
            children = new TrieNode[26];
        }
    }

    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();
            }
            curr = curr.children[idx];
        }
        curr.isEnd = true; // 标记完整单词终点
    }

    public boolean search(String word) {
        TrieNode node = findNode(word);
        // 路径存在且该结点是某单词结尾
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        // 前缀路径存在即可，不必 isEnd
        return findNode(prefix) != null;
    }

    // 沿 prefix/word 下行；中途缺边返回 null，否则返回终点结点
    private TrieNode findNode(String s) {
        TrieNode curr = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) {
                return null;
            }
            curr = curr.children[idx];
        }
        return curr;
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // ans：所有全排列
        List<List<Integer>> ans = new ArrayList<>();
        // used[i]：nums[i] 是否已在当前 path 中
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), ans);
        return ans;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path)); // 必须拷贝，path 会被后续修改
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            // 做选择
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, ans);
            // 撤销选择
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // ans：所有子集（含空集）
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), ans);
        return ans;
    }

    // start：本层可选起点；path：当前已选子集
    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(path)); // 每个状态都是一个合法子集
        if (start == nums.length) {
            return;
        }

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);              // 选择 nums[i]
            backtrack(nums, i + 1, path, ans); // 下一层只能从 i+1 继续
            path.remove(path.size() - 1);   // 撤销
        }
    }
}

class Solution {
    // mapping[d]：数字 d 对应的字母串；0、1 为空占位
    private static final String[] MAPPING = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.isEmpty()) {
            return ans; // 空输入无组合
        }
        backtrack(digits, 0, new StringBuilder(), ans);
        return ans;
    }

    // index：正在处理 digits 的第几位；sb：当前已选字母路径
    private void backtrack(String digits, int index, StringBuilder sb, List<String> ans) {
        if (index == digits.length()) {
            ans.add(sb.toString());
            return;
        }

        String letters = MAPPING[digits.charAt(index) - '0'];
        for (char ch : letters.toCharArray()) {
            sb.append(ch);                    // 做选择
            backtrack(digits, index + 1, sb, ans);
            sb.deleteCharAt(sb.length() - 1); // 撤销
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // ans：所有和为 target 的组合
        List<List<Integer>> ans = new ArrayList<>();
        // start=0, currSum=0：从数组开头开始选，当前路径和为 0
        backtrack(candidates, 0, 0, target, new ArrayList<>(), ans);
        return ans;
    }

    /**
     * @param start   本层可选起点下标；只选 [start..] 保证组合按原数组下标非降，去重
     * @param currSum 当前 path 中各数之和
     * @param path    正在构造的组合
     */
    private void backtrack(int[] candidates, int start, int currSum, int target,
                           List<Integer> path, List<List<Integer>> ans) {
        if (currSum == target) {
            ans.add(new ArrayList<>(path)); // 拷贝：path 后续还会被修改
            return;
        }
        // 和已超目标，或没有剩余候选可选
        if (currSum > target || start == candidates.length) {
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            // 传入 i（不是 i+1）：同一数字可再次被选；传入 start=i 仍禁止回到更小下标，防排列重复
            backtrack(candidates, i, currSum + candidates[i], target, path, ans);
            path.remove(path.size() - 1); // 去掉 candidates[i]，尝试本层下一个候选
        }
    }
}

class Solution {
    public List<String> generateParenthesis(int n) {
        // ans：所有合法括号串
        List<String> ans = new ArrayList<>();
        // left / right：当前路径中已使用的左、右括号个数；初始均为 0
        backtrack(n, 0, 0, new StringBuilder(), ans);
        return ans;
    }

    /**
     * @param n     目标括号对数
     * @param left  路径中已放入的 '(' 数量
     * @param right 路径中已放入的 ')' 数量
     * @param sb    当前正在构造的括号序列
     * @param ans   收集完整合法串
     */
    private void backtrack(int n, int left, int right,
                           StringBuilder sb, List<String> ans) {
        // 左右都用满 n 个：得到长度 2n 的合法串
        if (left == n && right == n) {
            ans.add(sb.toString());
            return;
        }

        // 还能放左括号：只要 left < n，多一个 '(' 不会破坏「右不超过左」的不变式
        if (left < n) {
            sb.append('(');
            backtrack(n, left + 1, right, sb, ans);
            sb.setLength(sb.length() - 1); // 去掉刚加的 '('，恢复供兄弟分支使用
        }

        // 能放右括号的充要条件：当前串中仍有未匹配的 '('，即 left > right
        // 若 right == left，再放 ')' 会出现前缀不合法（如 "())..."）
        if (left > right) {
            sb.append(')');
            backtrack(n, left, right + 1, sb, ans);
            sb.setLength(sb.length() - 1);
        }
    }
}

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) {
            return false;
        }
        int rows = board.length;
        int cols = board[0].length;
        // 每个格子都可能是单词起点
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 从格子 (i,j) 出发，尝试匹配 word 从下标 index 开始的后缀
     * @return 能否完整匹配完 word[index..]
     */
    private boolean dfs(char[][] board, int i, int j, int index, String word) {
        // 已匹配完所有字符（上一步刚吃掉最后一个字母后 index 增至 length）
        if (index == word.length()) {
            return true;
        }

        int rows = board.length;
        int cols = board[0].length;
        // 越界，或当前格不是目标字符（含已访问标记 '#'，也不等于 word[index]）
        if (i < 0 || j < 0 || i >= rows || j >= cols
                || board[i][j] != word.charAt(index)) {
            return false;
        }

        // 占用当前格：先保存原字符，再改成哨兵，避免同一路径重复走入
        char saved = board[i][j];
        board[i][j] = '#';

        // 四向任一方向能匹配剩余后缀即可；短路或，找到即停
        boolean found = dfs(board, i + 1, j, index + 1, word)
                || dfs(board, i - 1, j, index + 1, word)
                || dfs(board, i, j + 1, index + 1, word)
                || dfs(board, i, j - 1, index + 1, word);

        board[i][j] = saved; // 恢复棋盘，供其他起点/分支使用
        return found;
    }
}

class Solution {
    public List<List<String>> partition(String s) {
        // ans：所有「整串切成回文子串」的方案
        List<List<String>> ans = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), ans);
        return ans;
    }

    /**
     * @param start 当前待切分后缀的起始下标；表示 s[0..start) 已切好
     * @param path  已切出的回文子串序列
     */
    private void backtrack(String s, int start, List<String> path, List<List<String>> ans) {
        // 起点顶到串尾：前面每一段都是回文，得到一种完整分割
        if (start == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }

        // end：本段右开边界，从 start+1 切到 s.length()（至少切出 1 个字符）
        for (int end = start + 1; end <= s.length(); end++) {
            // 只有 s[start..end) 本身是回文，才能作为合法的一段
            if (!isPalindrome(s, start, end - 1)) {
                continue;
            }
            path.add(s.substring(start, end));
            // 下一段必须从 end 开始，保证覆盖整个字符串且不重叠
            backtrack(s, end, path, ans);
            path.remove(path.size() - 1); // 丢掉本段，尝试更长的 end
        }
    }

    // 判断 s[left..right]（闭区间）是否回文
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();

        // board：可变棋盘，每行一个 StringBuilder，便于 setCharAt
        List<StringBuilder> board = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            StringBuilder row = new StringBuilder();
            for (int j = 0; j < n; j++) {
                row.append('.');
            }
            board.add(row);
        }

        // occupiedCol[colIndex]：第 colIndex 列是否已有皇后
        boolean[] occupiedCol = new boolean[n];
        // antiDiag[row + colIndex]：副对角线 ↙（同行+列之和恒等，如 (0,3)(1,2)(2,1)）
        boolean[] antiDiag = new boolean[2 * n - 1];
        // mainDiag[row - colIndex + n - 1]：主对角线 ↘（行-列之差恒等；+n-1 映到 [0, 2n-2]）
        boolean[] mainDiag = new boolean[2 * n - 1];

        backtrack(board, 0, n, occupiedCol, antiDiag, mainDiag, ans);
        return ans;
    }

    /**
     * 在第 row 行放置一个皇后，并继续填后续行
     */
    private void backtrack(List<StringBuilder> board, int row, int n,
                           boolean[] occupiedCol, boolean[] antiDiag, boolean[] mainDiag,
                           List<List<String>> ans) {
        // 0..n-1 行都已放过：得到一种完整布局
        if (row == n) {
            List<String> snapshot = new ArrayList<>(n);
            for (StringBuilder sb : board) {
                snapshot.add(sb.toString());
            }
            ans.add(snapshot);
            return;
        }

        for (int colIndex = 0; colIndex < n; colIndex++) {
            int anti = row + colIndex;              // 副对角下标
            int main = row - colIndex + n - 1;      // 主对角下标
            // 该列或任一对角线已被占用则不能放
            if (occupiedCol[colIndex] || antiDiag[anti] || mainDiag[main]) {
                continue;
            }

            board.get(row).setCharAt(colIndex, 'Q');
            occupiedCol[colIndex] = antiDiag[anti] = mainDiag[main] = true;

            backtrack(board, row + 1, n, occupiedCol, antiDiag, mainDiag, ans);

            // 撤掉本行该列的皇后及相关占用，尝试下一列
            board.get(row).setCharAt(colIndex, '.');
            occupiedCol[colIndex] = antiDiag[anti] = mainDiag[main] = false;
        }
    }
}

class Solution {
    public int searchInsert(int[] nums, int target) {
        // left / right：闭区间 [left, right] 内可能存在 target，或插入点落在此范围及边界
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            // mid：防溢出写法，等价于 (left+right)/2
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid; // 题目保证无重复，找到即唯一下标
            }
            if (nums[mid] < target) {
                // mid 及左侧都 < target，插入点 / 目标只可能在 mid 右侧
                left = mid + 1;
            } else {
                // nums[mid] > target：mid 及右侧都太大，缩小到 mid 左侧
                right = mid - 1;
            }
        }
        // 未命中时：left 停在第一个 > target 的位置，也就是应按序插入的下标
        // （此时 right == left - 1，区间已被掏空）
        int ans = left;
        return ans;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        // left / right：把矩阵看成长度 m*n 的升序数组后的闭区间端点
        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 一维下标 mid → 二维坐标：每行 n 列，行号 mid/n，列号 mid%n
            int r = mid / n;
            int c = mid % n;
            int val = matrix[r][c];

            if (val == target) {
                return true;
            }
            if (val > target) {
                // mid 及右侧都 ≥ val > target，答案只可能在左侧
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 先找最左出现位置；没有则整段不存在
        int leftBound = findBound(nums, target, true);
        if (leftBound == -1) {
            return new int[]{-1, -1};
        }
        // 已知存在，再找最右出现位置
        int rightBound = findBound(nums, target, false);
        // ans：[起始下标, 结束下标]
        int[] ans = new int[]{leftBound, rightBound};
        return ans;
    }

    /**
     * @param findFirst true：找第一个等于 target 的下标；false：找最后一个
     * @return 找到则返回下标，否则 -1
     */
    private int findBound(int[] nums, int target, boolean findFirst) {
        int left = 0;
        int right = nums.length - 1;
        // found：二分过程中最近一次命中 target 的下标；可能被更左/更右的命中刷新
        int found = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                found = mid;
                if (findFirst) {
                    // 还想找更靠左的同值：收缩右边界，继续查左半
                    right = mid - 1;
                } else {
                    // 还想找更靠右的同值：收缩左边界，继续查右半
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return found;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            // nums[left..mid] 整体升序（旋转断点不在这段内）
            if (nums[mid] >= nums[left]) {
                // target 落在左半有序区间 [nums[left], nums[mid]) 内 → 去左
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    // 否则目标在断点一侧 / 右半，丢掉左半
                    left = mid + 1;
                }
            } else {
                // nums[mid..right] 整体升序（断点在 mid 左侧）
                // target 落在右半有序区间 (nums[mid], nums[right]] 内 → 去右
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        // 开闭：当 left == right 时区间只剩一个元素，必为最小值
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                // mid 落在较大的那段升序上，最小值一定在 mid 右边
                // 必须和 right 比：若和 left 比，像 [4,5,6,7,0,1,2] 会误判「左半有序」
                // 把 left 挪到 0 后，[0,1,2] 又与 left 同型，断点信息丢失
                left = mid + 1;
            } else {
                // nums[mid] <= nums[right]：mid 右侧（含 right）有序，最小值在左半含 mid
                // 故 right = mid（不能 mid-1，否则可能丢掉真正的最小值 mid）
                right = mid;
            }
        }
        // ans：最小元素
        int ans = nums[left];
        return ans;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 始终在较短数组上二分，保证 j = totalLeft - i 落在较长数组合法范围
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;

        // totalLeft：合并后左半应包含的元素个数；奇数时多带中间那个
        int totalLeft = (m + n + 1) / 2;

        // 二分的是「nums1 分给左半的个数 i」，范围 [0, m]
        int low = 0;
        int high = m;

        while (low < high) {
            // 取偏右的 mid，配合 low=i 避免死循环
            int i = low + (high - low + 1) / 2;
            int j = totalLeft - i; // nums2 分给左半的个数

            // nums1 左半最后一个 > nums2 右半第一个 → i 太大，左半偏大
            // （循环里 i≥1，故 i-1 安全；且 m≤n 保证 j 不会越界）
            if (nums1[i - 1] > nums2[j]) {
                high = i - 1;
            } else {
                // 当前 i 可行或偏小，尝试更大的 i
                low = i;
            }
        }

        int i = low;
        int j = totalLeft - i;

        // 边界用 ±∞ 哨兵：该侧没有元素时不影响 max/min
        int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];

        if ((m + n) % 2 == 1) {
            // 奇数：中位数就是左半的最大值
            return Math.max(nums1LeftMax, nums2LeftMax);
        }
        // 偶数：左半最大与右半最小的平均
        return (Math.max(nums1LeftMax, nums2LeftMax)
                + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
    }
}

class Solution {
    public boolean isValid(String s) {
        // stack：存放「尚未匹配的左括号所期望的右括号」，栈顶对应最近未闭合的左括号
        Deque<Character> stack = new ArrayDeque<>();

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(')'); // 之后必须先出现 ')' 才能闭合这对
            } else if (ch == '[') {
                stack.push(']');
            } else if (ch == '{') {
                stack.push('}');
            } else {
                // ch 是右括号：必须与栈顶期望一致；栈空说明没有对应左括号
                if (stack.isEmpty() || stack.pop() != ch) {
                    return false;
                }
            }
        }
        // 栈空：所有左括号都已按正确顺序闭合
        boolean ans = stack.isEmpty();
        return ans;
    }
}

class MinStack {
    // data：正常存所有入栈元素
    private final Deque<Integer> data;
    // minStack：栈顶始终是「当前 data 里的最小值」；仅在刷新最小值（含并列）时压入
    private final Deque<Integer> minStack;

    public MinStack() {
        data = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }

    public void push(int val) {
        data.push(val);
        // 空，或 val 不大于当前最小：成为（或并列成为）新的最小值，记一层
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        int val = data.pop();
        // 弹出的恰是当前最小值的一份拷贝：最小栈同步弹出，露出上一层最小值
        if (!minStack.isEmpty() && minStack.peek().equals(val)) {
            minStack.pop();
        }
    }

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

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

class Solution {
    public String decodeString(String s) {
        // curr：当前层正在拼接的字符串（尚未被外层倍数包裹完）
        StringBuilder curr = new StringBuilder();
        // count：当前层 '[' 前的重复次数；可能是多位数，需边读边累加
        int count = 0;
        // countStack：进入更内层 '[' 时，暂存外层的重复次数
        Deque<Integer> countStack = new ArrayDeque<>();
        // strStack：进入更内层时，暂存外层已经拼好的前缀
        Deque<StringBuilder> strStack = new ArrayDeque<>();

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                // 多位数字：如 "12[a]" 中先读到 1 再读到 2 → 12
                count = count * 10 + (ch - '0');
            } else if (ch == '[') {
                // 进入新一层：外层的「已有前缀」和「本层倍数」压栈保存
                countStack.push(count);
                strStack.push(curr);
                // 重置，开始专门构造括号内部的串
                count = 0;
                curr = new StringBuilder();
            } else if (ch == ']') {
                // 内层 curr 构造完毕：接到外层前缀上，并重复 times 次
                StringBuilder outer = strStack.pop();
                int times = countStack.pop();
                while (times-- > 0) {
                    outer.append(curr);
                }
                // 合并结果成为新的「当前层字符串」，继续往后扫
                curr = outer;
            } else {
                // 普通字母，直接追加到当前层
                curr.append(ch);
            }
        }
        return curr.toString();
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        // ans[i]：第 i 天要等几天才升温；默认 0 表示后面再也没有更高温
        int[] ans = new int[n];
        // stack：存下标；对应温度从栈底到栈顶单调不增（递减栈）
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 当前温度比栈顶那天更高：栈顶那天的「下一个更高」就是今天
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int j = stack.pop();
                ans[j] = i - j; // 间隔天数
            }
            // 今天也还没找到更暖的天，先入栈等后面来结算
            stack.push(i);
        }
        return ans;
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // h：原数组左右各加一个高度 0 的哨兵
        // 左哨兵：保证栈底有「比一切都矮」的柱，peek 永远安全
        // 右哨兵：扫到末尾时强制把栈里剩余柱子全部弹出结算
        int[] h = new int[n + 2];
        System.arraycopy(heights, 0, h, 1, n);

        // stack：存下标，对应高度严格递增（单调增栈）
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0); // 先压入左哨兵下标 0
        int ans = 0;

        for (int i = 1; i < n + 2; i++) {
            // 当前柱比栈顶更矮：栈顶柱的「右侧第一个更矮柱」就是 i
            while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
                int heightIndex = stack.pop();
                // 左边界：弹出后新的栈顶（左侧第一个 ≤ 当前高 的柱，含哨兵）
                // 可延伸宽度 = 右边界 i - 左边界 stack.peek() - 1
                int width = i - stack.peek() - 1;
                int area = width * h[heightIndex];
                ans = Math.max(ans, area);
            }
            stack.push(i);
        }
        return ans;
    }
}

class Solution {
    private static final Random RAND = new Random();

    public int findKthLargest(int[] nums, int k) {
        // targetIndex：升序排列后第 k 大所在下标（从 0 起）
        int targetIndex = nums.length - k;
        int left = 0;
        int right = nums.length - 1;

        while (true) {
            // pivotIndex：本轮划分后 pivot 的最终下标
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == targetIndex) {
                return nums[pivotIndex];
            }
            if (pivotIndex > targetIndex) {
                // 目标在 pivot 左侧更小的一段
                right = pivotIndex - 1;
            } else {
                left = pivotIndex + 1;
            }
        }
    }

    // 随机选 pivot，把区间排成「< pivot | pivot | > pivot」，返回 pivot 下标
    private int partition(int[] nums, int left, int right) {
        int pivotPos = left + RAND.nextInt(right - left + 1);
        int pivot = nums[pivotPos];
        swap(nums, pivotPos, left); // pivot 暂放到 left，方便双指针收拢

        int i = left + 1;
        int j = right;
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++; // 左侧应留下更小的，跳过已合法
            }
            while (i <= j && nums[j] > pivot) {
                j--; // 右侧应留下更大的
            }
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
            i++;
            j--;
        }
        // j 停在最后一个 ≤ pivot 的位置，与 left 交换后 pivot 就位
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // freq：数值 → 出现次数
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        // pq：小根堆，元素为 [数值, 频次]，按频次比较；只保留频次最高的 k 个
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            pq.offer(new int[]{e.getKey(), e.getValue()});
            if (pq.size() > k) {
                pq.poll(); // 丢掉当前 Top-K 中频次最小的
            }
        }

        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

class MedianFinder {
    // small：较小半边，大根堆；堆顶是较小半边的最大值（偏中位数左侧）
    private final PriorityQueue<Integer> small;
    // large：较大半边，小根堆；堆顶是较大半边的最小值（偏中位数右侧）
    private final PriorityQueue<Integer> large;

    public MedianFinder() {
        small = new PriorityQueue<>((a, b) -> b - a);
        large = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 先丢进较小半边，再把其中最大的挪到较大半边，保证分界有序
        small.offer(num);
        large.offer(small.poll());

        // 平衡个数：允许 small 比 large 多一个（奇数时中位数在 small）
        if (large.size() > small.size()) {
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if (small.size() == large.size()) {
            // 偶数：两堆顶是中间相邻两数
            return (small.peek() + large.peek()) / 2.0;
        }
        // 奇数：多出的那一个在 small 堆顶
        return small.peek();
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        // minPrice：截至前一天（含）见过的最低价，作为潜在买入点
        int minPrice = prices[0];
        // ans：全局最大利润；至少为 0（可以选择不交易）
        int ans = 0;

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price; // 更低的买入点，后面卖出更划算
            }
            // 假设今天卖出：利润 = 今日价 - 历史最低买入价
            ans = Math.max(ans, price - minPrice);
        }
        return ans;
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        // maxReach：从已访问过的格子出发，目前能跳到的最远下标
        int maxReach = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // 从 i 起跳，最远可到 i + nums[i]
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= n - 1) {
                return true; // 已经能覆盖最后一个下标
            }
            // i 走到了当前最远边界，且还没到终点：后面格子都够不着
            if (i >= maxReach) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public int jump(int[] nums) {
        int ans = 0;       // 最少跳跃次数
        int maxReach = 0;  // 在「当前这一跳」覆盖的格子里，继续起跳能到的最远下标
        int end = 0;       // 当前这一跳的右边界（走到这里就必须再跳一次）
        int n = nums.length;

        // 不用访问最后一个下标：若已能覆盖终点，不必从终点再起跳
        for (int i = 0; i < n - 1; i++) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (i == end) {
                // 本跳区间扫完，必须再跳一次，新边界变成刚才积累的最远可达
                ans++;
                end = maxReach;
                if (end >= n - 1) {
                    return ans; // 新边界已盖过终点，答案已确定
                }
            }
        }
        return ans;
    }
}

class Solution {
    public List<Integer> partitionLabels(String s) {
        // lastIndex[c - 'a']：字母 c 在 s 中最后一次出现的下标
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i) - 'a'] = i;
        }

        List<Integer> ans = new ArrayList<>();
        int maxReach = 0; // 当前片段必须至少延伸到的最右下标
        int left = 0;     // 当前片段左端

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 片段内一旦出现 ch，就必须覆盖到它的最后一次出现
            maxReach = Math.max(maxReach, lastIndex[ch - 'a']);
            if (i == maxReach) {
                // 走到本片段右端：中间出现过的字母都不会再出现在后面
                ans.add(i - left + 1);
                left = maxReach + 1; // 下一段从右端的下一个位置开始
            }
        }
        return ans;
    }
}

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n; // 1 阶只有 1 种；2 阶有 1+1 / 2 两种
        }
        int prev1 = 1; // f(i-2)：爬到 i-2 阶的方法数
        int prev2 = 2; // f(i-1)：爬到 i-1 阶的方法数
        int ans = 0;
        for (int i = 3; i <= n; i++) {
            ans = prev2 + prev1; // f(i) = f(i-1) + f(i-2)
            prev1 = prev2;
            prev2 = ans;
        }
        return ans;
    }
}

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>(numRows); // 预分配行数容量
        ans.add(List.of(1)); // 第 0 行只有 [1]

        for (int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<>(i + 1); // 第 i 行有 i+1 个数
            row.add(1); // 左端始终为 1
            // 中间：取上一行左上 prev[j-1] 与右上 prev[j] 之和
            for (int j = 1; j < i; j++) {
                row.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
            }
            row.add(1); // 右端始终为 1
            ans.add(row);
        }
        return ans;
    }
}

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // prev1 = dp[i-2]：偷到第 i-2 间为止的最高金额
        // prev2 = dp[i-1]：偷到第 i-1 间为止的最高金额
        int prev1 = nums[0];
        int prev2 = Math.max(nums[0], nums[1]);
        int ans = prev2;

        for (int i = 2; i < nums.length; i++) {
            // 偷第 i 间：prev1 + nums[i]；不偷：prev2
            ans = Math.max(prev1 + nums[i], prev2);
            prev1 = prev2;
            prev2 = ans;
        }
        return ans;
    }
}

class Solution {
    public int numSquares(int n) {
        // dp[i]：和为 i 时，完全平方数的最少个数
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 1); // 用不可能达到的上界当「未算出」哨兵（最多拆成 n 个 1）
        dp[0] = 0; // 和为 0 不需要任何平方数

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                // 选一个 j²，剩余 i-j² 的最优再 +1
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        int ans = dp[n];
        return ans;
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        // dp[j]：凑出金额 j 所需的最少硬币数
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // 哨兵：比「全用 1 元」还大，表示尚不可达
        dp[0] = 0;

        for (int coin : coins) {
            // 从小到大：同一枚硬币可被多次计入（完全背包）
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }

        int ans = (dp[amount] == amount + 1) ? -1 : dp[amount];
        return ans;
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> dict = new HashSet<>(wordDict);
        // dp[i]：前缀 s[0..i)（前 i 个字符）能否被字典拆分
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 空前缀视为可拆分

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // 左段可拆分，且右段 s[j..i) 是一个字典词（substring 左闭右开）
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 找到一种切法即可
                }
            }
        }
        boolean ans = dp[n];
        return ans;
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp[i]：以 nums[i] 结尾的最长严格递增子序列长度
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 单个元素自身构成长度为 1 的子序列
        int ans = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 只有严格大于才能接在 j 后面
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // imax / imin：以当前下标结尾的子数组乘积的最大 / 最小值
        int imax = nums[0];
        int imin = nums[0];
        int ans = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num < 0) {
                // 乘负数后：原最大变最小、原最小变最大，先交换再统一更新
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            // 也可以从当前元素重新开始一段子数组
            imax = Math.max(num, imax * num);
            imin = Math.min(num, imin * num);
            ans = Math.max(ans, imax);
        }
        return ans;
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        if (total % 2 != 0) {
            return false; // 奇数无法均分成两个相等和
        }
        int target = total / 2; // 等价于：能否选出子集和为 target
        // dp[j]：是否存在子集，元素和恰好为 j
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // 空子集和为 0

        for (int num : nums) {
            // 倒序：同一轮里每个 num 最多用一次（0-1 背包）
            for (int j = target; j >= num; j--) {
                // 不选 num 保持 dp[j]；选 num 则看 j-num 是否可达
                dp[j] = dp[j] || dp[j - num];
            }
        }
        boolean ans = dp[target];
        return ans;
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int ans = 0;
        int left = 0;  // 当前段内 '(' 个数（右扫时改为 ')' 个数）
        int right = 0; // 当前段内 ')' 个数（右扫时改为 '(' 个数）

        // 从左到右：处理「右边多 ')'」导致断开的情况
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left < right) {
                // ')' 比 '(' 多，无法再配平，重新开始
                left = right = 0;
            } else if (left == right) {
                // 恰好配平才是合法连续子串
                ans = Math.max(ans, right * 2);
            }
            // left > right：前面多 '('，先继续数，等右扫再处理
        }

        // 从右到左：处理「左边多 '('」导致左扫算不全的情况
        left = right = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == ')') {
                left++;  // 从右看，')' 充当开口
            } else {
                right++; // '(' 充当闭合
            }
            if (left < right) {
                left = right = 0;
            } else if (left == right) {
                ans = Math.max(ans, right * 2);
            }
        }
        return ans;
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[j]：当前处理到某一行时，到达第 j 列的路径数
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 第一行全为 1；且每行第 0 列始终为 1（只会一直向下）

        for (int i = 1; i < m; i++) { // 从第 2 行开始
            for (int j = 1; j < n; j++) {
                // dp[j]（尚未更新）= 上一行同列；dp[j-1] = 本行左列
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        int ans = dp[n - 1];
        return ans;
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        // 第一行：只能一直向右，前缀累加
        for (int j = 1; j < col; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        // 第一列：只能一直向下，前缀累加
        for (int i = 1; i < row; i++) {
            grid[i][0] += grid[i - 1][0];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                // 从左或从上走来，选路径和更小的那条
                grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        int ans = grid[row - 1][col - 1];
        return ans;
    }
}

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }

        int maxLen = 1; // 当前最长回文长度
        int begin = 0;  // 最长回文的起始下标
        // dp[i][j]：子串 s[i..j]（含两端）是否为回文
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true; // 单字符必是回文
        }

        // 按长度 L 枚举，保证算 dp[i][j] 时 dp[i+1][j-1] 已就绪
        for (int L = 2; L <= n; L++) {
            for (int i = 0; i < n; i++) {
                int j = i + L - 1; // 右端：使区间长度为 L
                if (j >= n) {
                    break;
                }

                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else if (j - i < 3) {
                    // 长度 2（aa）或 3（aba）：首尾相同即回文
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }

                if (dp[i][j] && L > maxLen) {
                    maxLen = L;
                    begin = i;
                }
            }
        }

        String ans = s.substring(begin, begin + maxLen);
        return ans;
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // dp[i][j]：text1[0..i) 与 text2[0..j) 的最长公共子序列长度
        int[][] dp = new int[m + 1][n + 1]; // 默认 0：空串与任意串的 LCS 为 0

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 当前字符可纳入公共子序列
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 不相等：丢掉 text1 末尾 或 丢掉 text2 末尾，取更长者
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int ans = dp[m][n];
        return ans;
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        // dp[i][j]：word1[0..i) 变成 word2[0..j) 的最少操作数
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // word2 为空：删除 word1 的 i 个字符
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // word1 为空：插入 word2 的 j 个字符
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // 相同：无需操作
                } else {
                    int del = dp[i - 1][j] + 1;     // 删除 word1[i-1]
                    int ins = dp[i][j - 1] + 1;     // 插入 word2[j-1]
                    int rep = dp[i - 1][j - 1] + 1; // 把 word1[i-1] 替换成 word2[j-1]
                    dp[i][j] = Math.min(del, Math.min(ins, rep));
                }
            }
        }
        int ans = dp[m][n];
        return ans;
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num; // 相同数异或为 0，最终只剩出现一次的那个
        }
        return ans;
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0]; // 当前假设的多数元素
        int cnt = 0;             // 候选人相对票数（遇同 +1，遇异 -1）

        for (int num : nums) {
            if (cnt == 0) {
                candidate = num; // 票数耗尽，换当前数为新候选人
            }
            if (candidate == num) {
                cnt++;
            } else {
                cnt--; // 与候选人不同：一对一抵消
            }
        }
        int ans = candidate; // 题目保证一定存在多数元素，无需二次校验
        return ans;
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0; // 下一个 0 应写入的下标
        int p1 = 0; // 下一个 1 应写入的下标

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            nums[i] = 2; // 先按「最右颜色」落子，后面若是 0/1 再覆盖回来
            if (num <= 1) {
                nums[p1++] = 1; // 0 和 1 都先占一个 1 的坑
            }
            if (num == 0) {
                nums[p0++] = 0; // 真正的 0 覆盖刚才写下的 1
            }
        }
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return;
        }

        // 从右往左找第一个升序对：nums[i] < nums[i+1]，i 是要变大的位置
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i < 0) {
            reverse(nums, 0, n - 1); // 整体递减：已是最大排列，翻成最小
            return;
        }

        // 在 i 右侧（递减后缀）从右找第一个 > nums[i] 的数，保证变幅最小
        int j = n - 1;
        while (j > i && nums[i] >= nums[j]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1, n - 1); // 后缀原本递减，反转后变成最小升序
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

class Solution {
    public int findDuplicate(int[] nums) {
        // 将 i → nums[i] 视为链表；重复值对应环入口
        int slow = 0;
        int fast = 0;

        while (true) {
            slow = nums[slow];           // 慢指针走一步
            fast = nums[nums[fast]];     // 快指针走两步
            if (slow == fast) {
                // 相遇后：一个从起点、一个从相遇点，同步走一步
                slow = 0;
                while (slow != fast) {
                    slow = nums[slow];
                    fast = nums[fast];
                }
                int ans = slow; // 再次相遇即为环入口 = 重复数
                return ans;
            }
        }
    }
}