LeetCode 852, 20, 51

852. 山脉数组的峰顶索引

题目链接

852. 山脉数组的峰顶索引

二分

思路

本题的 arr 是 先递增，后递减 的，共有如下两种情况：

对于第一种情况：中间值的前一个值大于中间值，可以发现：最大值在左子区间上。

最大值在左子区间上
对于第二种情况：中间值的前一个值小于中间值，可以发现：最大值在右子区间上。

代码

java">class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1 >> 1); // 中间值的索引
            if (arr[mid - 1] < arr[mid]) { // 中间值的前一个值 小于 中间值
                left = mid; // 最大值在右子区间上
            } else { // 中间值的前一个值 大于 中间值
                right = mid - 1; // 最大值在左子区间上
            }
        }
        return left;
    }
}

三分

思路

寻找峰值是三分的经典用法，三分与二分类似，都是将区间平均分，不过三分把区间分成三份，比较左三等分点和右三等分点指向的值的大小，从而决定选择查找哪个区间。

当 左三等分点指向的值小于右三等分指向的值 时，说明 最大值点在右边的 $\frac{2}{3}$ 区间。
alt text
当 左三等分点指向的值大于右三等分指向的值 时，说明 最大值点在左边的 $\frac{2}{3}$ 区间。

代码

java">class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int midL = left + (right - left) / 3, midR = right - (right - left) / 3;
            if (arr[midL] < arr[midR]) { // 左三等分点指向的值 小于 右三等分指向的值
                left = midL + 1; // 最大值点在右边的 2/3 区间
            } else { // 左三等分点指向的值 大于 右三等分指向的值
                right = midR - 1; // 最大值点在左边的 2/3 区间
            }
        }
        return left;
    }
}

20. 有效的括号

题目链接

20. 有效的括号

思路

有效字符串需满足：

左括号必须用 相同类型 的右括号闭合。
左括号必须以 正确的顺序 闭合。这就说明 "[(])" 不是有效字符串，而 "([])" 是有效字符串。
每个右括号都有一个对应的相同类型的左括号。

注意有效字符串的以上三个条件，尤其是第二个条件。由 "[(])" 不是有效字符串可知：对于一个右括号，它要匹配它前面的最后一个左括号。由 "([])" 是有效字符串可知：被右括号成功匹配之后的左括号可以视而不见。

这样的判断驱使着我们使用栈这种数据结构来存储左括号，对于字符串 s 中的每一个字符 ch (顺序遍历)，有以下的操作：

如果 ch 是左括号，直接将其放入栈中。
如果 ch 是右括号，判断栈顶元素 (这里的栈顶元素就是 ch 前面的最后一个左括号) 是否能与 ch 匹配，如果不能，则返回 false；否则将匹配成功的左括号 (即栈顶元素) 弹出栈，并继续遍历下一个字符。
此外，可能会遇到 当 ch 是右括号时，栈为空 的情况，例如 "]", "()}"，对于第一个字符串，当 ch == ']' 时，栈为空；对于第二个字符串，当 ch == '}' 时，栈为空。此时直接返回 false 即可。

遍历完所有字符后，不能直接返回 true，因为此时栈可能不为空，例如对于 "[({"，栈最后还存储着三个左括号，此时应该返回 false；如果最后的栈为空，则可以放心地返回 true。

代码

java">class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>(); // 储存 左括号 的栈
        for (char ch : s.toCharArray()) { // 从字符串 s 中拿出字符 ch 进行操作
            if (ch == '(' || ch == '{' || ch == '[') { // 如果是左括号之一
                stack.push(ch); // 则将其放入栈中
                continue; // 不进行接下来的操作
            }

            // 否则 ch 是右括号，需要给它匹配相应的左括号

            if (stack.isEmpty()) { // 如果栈中没有元素
                return false; // 则无法匹配，返回 false
            }

            // 否则栈中有元素，这时开始匹配

            if ((ch == ')' && stack.peek() != '(')              // 如果 ')' 匹配不到 '('
                    || (ch == '}' && stack.peek() != '{')       // 或者 '}' 匹配不到 '{'
                    || (ch == ']' && stack.peek() != '[')) {    // 或者 ']' 匹配不到 '['
                return false; // 则 ch 没有 正确顺序的左括号 与之匹配，返回 false
            }

            // 否则 ch 有 正确顺序的左括号 与之匹配

            stack.pop(); // 将 匹配过的左括号 从栈中删除
        }

        return stack.isEmpty(); // 如果栈中还有元素，说明没有匹配成功，返回 false；否则返回 true
    }
}

51. N 皇后

题目链接

51. N 皇后

思路

回溯

本题的困难标签有些夸张了，使用基本的回溯就可以解决。

题目要求把皇后放到无法攻击的位置上，皇后能攻击到的对象为 同一行、同一列、同一左斜线 (左斜线指的是从左上到右下的斜线↘️)、同一右斜线 (右斜线指的是从右上到左下的斜线↙️) 的对象。既然要求在 n×n 的棋盘上要放置 n 个皇后，那么 每一行和每一列都必须有皇后，并且在一条 左斜线 和 右斜线 上不能同时存在多个皇后。

可以想到，使用回溯对 每一行 进行操作：在 每一行 中枚举 每一列 来放置皇后，前提是 在这一列、这一左斜线、这一右斜线上不存在皇后，如果能放置，就按照回溯的常规做法：

将皇后放到棋盘的当前位置上。
标记皇后在这一列、这一左斜线、这一右斜线上。
放置下一个皇后。
取消标记。
将当前皇后从棋盘上移除。

完全可以改变回溯的策略，即对 每一列 进行操作：在 每一列 中枚举 每一行 来放置皇后。

如何保证皇后之间无法互相攻击

本题除回溯思想比较难想到之外，还有一个难点：如何保证皇后之间无法互相攻击？上面其实已经提到过了，就是防止皇后被放到相同的 行、列、左斜线或右斜线 上，行和列都很直观，但左、右斜线就不是那么直观了，得使用行和列进行简单的计算。

下图是一个 4×4 的棋盘，标记了每个元素所对应的左、右斜线的编号，从 0 开始，到 2 * 4 - 1 - 1 = 6 结束，可以得到：在 n×n 的棋盘上，对于第 i 行、第 j 列的元素，它的左斜线的编号为 n - (i - j) - 1，右斜线的编号为 i + j。
四皇后问题

代码

java">class Solution {
    public List<List<String>> solveNQueens(int n) {
        // 初始化本对象的属性
        this.n = n;
        this.col = new boolean[n];
        this.lSlash = new boolean[2 * n - 1];
        this.rSlash = new boolean[2 * n - 1];
        this.table = new char[n][n];
        for (char[] row : table) { // 将棋盘的每行都填充为 '.'
            Arrays.fill(row, '.');
        }

        dfs(0);
        return res;
    }

    private List<List<String>> res = new ArrayList<>(); // 存储结果的集合
    private char[][] table; // 棋盘
    private int n; // 棋盘的 行数 和 列数
    private boolean[] col; // 判断 某一列 是否有皇后
    private boolean[] lSlash; // 判断 某一左斜线(左上 到 右下) 是否有皇后
    private boolean[] rSlash; // 判断 某一右斜线(右上 到 左下) 是否有皇后

    // 在索引为 i 的行上，放置第 i+1 个皇后
    private void dfs(int i) {
        if (i == n) { // 如果已经放置够了 n 个皇后
            // 将 放置皇后的棋盘 加入到结果集合中
            List<String> ans = new ArrayList<>();
            for (char[] row : table) {
                ans.add(new String(row));
            }
            res.add(ans);
            return; // 并直接返回
        }

        for (int j = 0; j < n; j++) { // 枚举所有的 列
            int ls = n - (i - j) - 1; // 当前行列对应的 左斜线的编号
            int rs = i + j; // 当前行列对应的 右斜线的编号

            // 如果 这列、左斜线、右斜线 之一被占，则取消本次放置
            if (col[j] || lSlash[ls] || rSlash[rs]) {
                continue;
            }

            table[i][j] = 'Q'; // 将皇后放到棋盘的当前位置上
            col[j] = lSlash[ls] = rSlash[rs] = true; // 标记皇后在这一列、这一左斜线、这一右斜线上

            dfs(i + 1); // 放置下一个皇后

            col[j] = lSlash[ls] = rSlash[rs] = false; // 取消标记
            table[i][j] = '.'; // 将当前皇后从棋盘上移除
        }
    }
}