❌

普通视图

发现新文章，点击刷新页面。
今天 — 2025年12月29日LeetCode 每日一题题解

每日一题-金字塔转换矩阵🟡

✇LeetCode 每日一题题解
2025年12月29日 00:00

你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行 少一个块 ，并且居中。

为了使金字塔美观，只有特定的 三角形图案 是允许的。一个三角形的图案由 两个块 和叠在上面的 单个块 组成。模式是以三个字母字符串的列表形式 allowed 给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。

  • 例如，"ABC" 表示一个三角形图案，其中一个 “C” 块堆叠在一个 'A' 块(左)和一个 'B' 块(右)之上。请注意，这与 "BAC" 不同，"B" 在左下角，"A" 在右下角。

你从作为单个字符串给出的底部的一排积木 bottom 开始，必须 将其作为金字塔的底部。

在给定 bottom 和 allowed 的情况下，如果你能一直构建到金字塔顶部，使金字塔中的 每个三角形图案 都是在 allowed 中的，则返回 true ，否则返回 false 。

 

示例 1：

输入：bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
输出：true
解释：允许的三角形图案显示在右边。
从最底层(第 3 层)开始，我们可以在第 2 层构建“CE”，然后在第 1 层构建“E”。
金字塔中有三种三角形图案，分别是 “BCC”、“CDE” 和 “CEA”。都是允许的。

示例 2：

输入：bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
输出：false
解释：允许的三角形图案显示在右边。
从最底层(即第 4 层)开始，创造第 3 层有多种方法，但如果尝试所有可能性，你便会在创造第 1 层前陷入困境。

 

提示：

  • 2 <= bottom.length <= 6
  • 0 <= allowed.length <= 216
  • allowed[i].length == 3
  • 所有输入字符串中的字母来自集合 {'A', 'B', 'C', 'D', 'E', 'F'}。
  •  allowed 中所有值都是 唯一的

【图解】回溯 + vis 优化 + 位运算优化（Python/Java/C++/Go）

✇LeetCode 每日一题题解
作者 endlesscheng
2025年12月26日 16:49

写一个类似 17. 电话号码的字母组合 的回溯（搜索）。从下往上，从左到右，枚举金字塔的每个格子填什么字母。

lc756-1.png{:width=600px}

比如 $\textit{allowed}$ 中有 $\texttt{AAB}$ 和 $\texttt{AAC}$，那么当 $(i+1,j)$ 和 $(i+1,j+1)$ 都填 $\texttt{A}$ 的时候，$(i,j)$ 可以填 $\texttt{B}$，也可以填 $\texttt{C}$。枚举填哪个。

为了快速知道 $\texttt{AA}\to [\texttt{B}, \texttt{C}]$ 的对应关系，可以把 $\textit{allowed}$ 用哈希表（或者二维数组）分组，把 $\textit{allowed}[i]$ 前两个字母对应的第三个字母，记录在一个列表中。

优化前

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)  # 三角形底部两个字母 -> [三角形顶部字母]
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[''] * (i + 1) for i in range(n)]
        pyramid[-1] = bottom

        # 现在准备填 (i, j) 这个格子
        # 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
        def dfs(i: int, j: int) -> bool:
            if i < 0:  # 所有格子都已填完
                return True

            if j == i + 1:  # i 行已填完
                return dfs(i - 1, 0)  # 开始填 i-1 行

            # 枚举 (i, j) 填什么字母
            # 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        # 从倒数第二行开始填
        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        // 三角形底部两个字母 -> [三角形顶部字母]
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        // 从倒数第二行开始填
        return dfs(n - 2, 0, pyramid, groups);
    }

    // 现在准备填 (i, j) 这个格子
    // 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
    private boolean dfs(int i, int j, char[][] pyramid, List<Character>[][] groups) {
        if (i < 0) { // 所有格子都已填完
            return true;
        }

        if (j == i + 1) { // i 行已填完
            return dfs(i - 1, 0, pyramid, groups); // 开始填 i-1 行
        }

        // 枚举 (i, j) 填什么字母
        // 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6]{}; // 三角形底部两个字母 -> [三角形顶部字母]
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        for (int i = 0; i < n - 1; i++) {
            pyramid[i].resize(i + 1);
        }
        pyramid[n - 1] = move(bottom);

        // 现在准备填 (i, j) 这个格子
        // 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) { // 所有格子都已填完
                return true;
            }

            if (j == i + 1) { // i 行已填完
                return dfs(i - 1, 0); // 开始填 i-1 行
            }

            // 枚举 (i, j) 填什么字母
            // 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i][j] = top;
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        // 从倒数第二行开始填
        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{} // 三角形底部两个字母 -> [三角形顶部字母]
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

// 现在准备填 (i, j) 这个格子
// 返回继续填能否填完所有格子（从下往上填，每行从左到右填）
var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 { // 所有格子都已填完
return true
}

if j == i+1 { // i 行已填完
return dfs(i-1, 0) // 开始填 i-1 行
}

// 枚举 (i, j) 填什么字母
// 这取决于 (i+1, j) 和 (i+1, j+1) 填的字母
for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

// 从倒数第二行开始填
return dfs(n-2, 0)
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(|\Sigma|^{n^2})$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。搜索树的高度为 $\mathcal{O}(n^2)$，每个节点至多有 $|\Sigma|$ 个儿子，所以搜索树有 $\mathcal{O}(|\Sigma|^{n^2})$ 个节点，遍历这棵搜索树需要 $\mathcal{O}(|\Sigma|^{n^2})$ 的时间。
  • 空间复杂度：$\mathcal{O}(m + n^2)$，其中 $m$ 是 $\textit{allowed}$ 的长度。

优化一：减少重复搜索

lc756-2c.png{:width=600px}

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[''] * (i + 1) for i in range(n)]
        pyramid[-1] = bottom

        vis = set()  # 访问标记

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            if j == i + 1:
                row = ''.join(pyramid[i])
                if row in vis:  # 这一行之前填过一模一样的，继续填，没能填到塔顶
                    return False  # 直接返回
                vis.add(row)
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        Set<String> vis = new HashSet<>(); // 访问标记

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, char[][] pyramid, Set<String> vis, List<Character>[][] groups) {
        if (i < 0) {
            return true;
        }

        if (j == i + 1) {
            String row = new String(pyramid[i]);
            if (!vis.add(row)) { // 这一行之前填过一模一样的，继续填，没能填到塔顶
                return false; // 直接返回
            }
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6];
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        for (int i = 0; i < n - 1; i++) {
            pyramid[i].resize(i + 1);
        }
        pyramid[n - 1] = move(bottom);

        unordered_set<string> vis; // 访问标记

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (j == i + 1) {
                if (!vis.insert(pyramid[i]).second) { // 这一行之前填过一模一样的，继续填，没能填到塔顶
                    return false; // 直接返回
                }
                return dfs(i - 1, 0);
            }

            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i][j] = top;
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{}
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

vis := map[string]struct{}{} // 访问标记

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

if j == i+1 {
row := string(pyramid[i])
if _, ok := vis[row]; ok { // 这一行之前填过一模一样的，继续填，没能填到塔顶
return false // 直接返回
}
vis[row] = struct{}{}
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

优化二：减少更多重复搜索

lc756-3c.png{:width=600px}

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = defaultdict(list)
        for s in allowed:
            groups[s[:2]].append(s[2])

        n = len(bottom)
        pyramid = [[] for _ in range(n)]
        pyramid[-1] = bottom

        vis = set()

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            row = ''.join(pyramid[i])
            if row in vis:  # 之前填过一模一样的，这个局部的金字塔无法填完
                return False  # 继续递归也无法填完，直接返回

            if j == i + 1:
                vis.add(row)
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1][j] + pyramid[i + 1][j + 1]]:
                pyramid[i].append(top)
                if dfs(i, j + 1):
                    return True
                pyramid[i].pop()
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Character>[][] groups = new ArrayList[6][6];
        for (List<Character>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            groups[s[0] - 'A'][s[1] - 'A'].add(s[2]);
        }

        int n = bottom.length();
        char[][] pyramid = new char[n][];
        for (int i = 0; i < n - 1; i++) {
            pyramid[i] = new char[i + 1];
        }
        pyramid[n - 1] = bottom.toCharArray();

        Set<String> vis = new HashSet<>();

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, char[][] pyramid, Set<String> vis, List<Character>[][] groups) {
        if (i < 0) {
            return true;
        }

        String row = new String(pyramid[i], 0, j);
        if (vis.contains(row)) { // 之前填过一模一样的，这个局部的金字塔无法填完
            return false; // 继续递归也无法填完，直接返回
        }

        if (j == i + 1) {
            vis.add(row);
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
            pyramid[i][j] = top;
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        string groups[6][6];
        for (auto& s : allowed) {
            groups[s[0] - 'A'][s[1] - 'A'] += s[2];
        }

        int n = bottom.size();
        vector<string> pyramid(n);
        pyramid[n - 1] = move(bottom);

        unordered_set<string> vis;

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (vis.contains(pyramid[i])) { // 之前填过一模一样的，这个局部的金字塔无法填完
                return false; // 继续递归也无法填完，直接返回
            }

            if (j == i + 1) {
                vis.insert(pyramid[i]);
                return dfs(i - 1, 0);
            }

            for (char top : groups[pyramid[i + 1][j] - 'A'][pyramid[i + 1][j + 1] - 'A']) {
                pyramid[i] += top;
                if (dfs(i, j + 1)) {
                    return true;
                }
                pyramid[i].pop_back();
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [6][6][]byte{}
for _, s := range allowed {
a, b := s[0]-'A', s[1]-'A'
groups[a][b] = append(groups[a][b], s[2])
}

n := len(bottom)
pyramid := make([][]byte, n)
for i := range n - 1 {
pyramid[i] = make([]byte, i+1)
}
pyramid[n-1] = []byte(bottom)

vis := map[string]struct{}{}

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

row := string(pyramid[i][:j])
if _, ok := vis[row]; ok { // 之前填过一模一样的，这个局部的金字塔无法填完
return false // 继续递归也无法填完，直接返回
}

if j == i+1 {
vis[row] = struct{}{}
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1][j]-'A'][pyramid[i+1][j+1]-'A'] {
pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n|\Sigma|^n)$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。把字符串按照长度分类，长为 $k$ 的字符串至多有 $|\Sigma|^k$ 个。等比数列求和 $|\Sigma| + |\Sigma|^2 + \cdots + |\Sigma|^{n-1} = \mathcal{O}(|\Sigma|^n)$。一共有 $\mathcal{O}(|\Sigma|^n)$ 个字符串，每个字符串花费 $\mathcal{O}(n)$ 的时间与 $\textit{vis}$ 交互（查询，插入）。
  • 空间复杂度：$\mathcal{O}(n|\Sigma|^n)$。$\textit{vis}$ 保存了 $\mathcal{O}(|\Sigma|^n)$ 个字符串，每个字符串需要 $\mathcal{O}(n)$ 的空间。

优化三：位运算

把 $\texttt{A}$ 到 $\texttt{F}$ 映射为 $1$ 到 $6$。由于每个字母只占用 $3$ 个比特位，可以用二进制数表示字符串。

由于倒数第二排最多 $5$ 个字母，所以记录到 $\textit{vis}$ 中的二进制数的长度最多为 $15$。

问：为什么不映射为 $0$ 到 $5$？

答：比如，我们无法区分 $\texttt{AA}$ 和 $\texttt{AAA}$，二者都是 $0$。

###py

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        groups = [[[] for _ in range(7)] for _ in range(7)]
        for a, b, c in allowed:
            # A~F -> 1~6
            groups[ord(a) & 31][ord(b) & 31].append(ord(c) & 31)

        n = len(bottom)
        pyramid = [0] * n
        for i, ch in enumerate(bottom):
            pyramid[-1] |= (ord(ch) & 31) << (i * 3)  # 等价于 pyramid[-1][i] = ord(ch)&31

        vis = set()

        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return True

            if pyramid[i] in vis:
                return False

            if j == i + 1:
                vis.add(pyramid[i])
                return dfs(i - 1, 0)

            for top in groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]:
                pyramid[i] &= ~(7 << (j * 3))  # 清除之前填的字母，等价于 pyramid[i][j] = 0
                pyramid[i] |= top << (j * 3)  # 等价于 pyramid[i][j] = top
                if dfs(i, j + 1):
                    return True
            return False

        return dfs(n - 2, 0)

###java

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        List<Integer>[][] groups = new ArrayList[7][7];
        for (List<Integer>[] row : groups) {
            Arrays.setAll(row, _ -> new ArrayList<>());
        }
        for (String S : allowed) {
            char[] s = S.toCharArray();
            // A~F -> 1~6
            groups[s[0] & 31][s[1] & 31].add(s[2] & 31);
        }

        char[] s = bottom.toCharArray();
        int n = s.length;
        int[] pyramid = new int[n];
        for (int i = 0; i < n; i++) {
            pyramid[n - 1] |= (s[i] & 31) << (i * 3); // 等价于 pyramid[n-1][i] = s[i]&31
        }

        boolean[] vis = new boolean[1 << ((n - 1) * 3)];

        return dfs(n - 2, 0, pyramid, vis, groups);
    }

    private boolean dfs(int i, int j, int[] pyramid, boolean[] vis, List<Integer>[][] groups) {
        if (i < 0) {
            return true;
        }

        if (vis[pyramid[i]]) {
            return false;
        }

        if (j == i + 1) {
            vis[pyramid[i]] = true;
            return dfs(i - 1, 0, pyramid, vis, groups);
        }

        for (int top : groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]) {
            pyramid[i] &= ~(7 << (j * 3)); // 清除之前填的字母，等价于 pyramid[i][j] = 0
            pyramid[i] |= top << (j * 3); // 等价于 pyramid[i][j] = top
            if (dfs(i, j + 1, pyramid, vis, groups)) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        vector<int> groups[7][7];
        for (auto& s : allowed) {
            // A~F -> 1~6
            groups[s[0] & 31][s[1] & 31].push_back(s[2] & 31);
        }

        int n = bottom.size();
        vector<int> pyramid(n);
        for (int i = 0; i < n; i++) {
            pyramid[n - 1] |= (bottom[i] & 31) << (i * 3); // 等价于 pyramid[n-1][i] = bottom[i]&31
        }

        vector<uint8_t> vis(1 << ((n - 1) * 3));

        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return true;
            }

            if (vis[pyramid[i]]) {
                return false;
            }

            if (j == i + 1) {
                vis[pyramid[i]] = true;
                return dfs(i - 1, 0);
            }

            for (int top : groups[pyramid[i + 1] >> (j * 3) & 7][pyramid[i + 1] >> ((j + 1) * 3) & 7]) {
                pyramid[i] &= ~(7 << (j * 3)); // 清除之前填的字母，等价于 pyramid[i][j] = 0
                pyramid[i] |= top << (j * 3); // 等价于 pyramid[i][j] = top
                if (dfs(i, j + 1)) {
                    return true;
                }
            }
            return false;
        };

        return dfs(n - 2, 0);
    }
};

###go

func pyramidTransition(bottom string, allowed []string) bool {
groups := [7][7][]byte{}
for _, s := range allowed {
a, b := s[0]&31, s[1]&31 // A~F -> 1~6
groups[a][b] = append(groups[a][b], s[2]&31)
}

n := len(bottom)
pyramid := make([]int, n)
for i, ch := range bottom {
pyramid[n-1] |= int(ch&31) << (i * 3) // 等价于 pyramid[n-1][i] = ch&31
}

vis := make([]bool, 1<<((n-1)*3))

var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return true
}

if vis[pyramid[i]] {
return false
}

if j == i+1 {
vis[pyramid[i]] = true
return dfs(i-1, 0)
}

for _, top := range groups[pyramid[i+1]>>(j*3)&7][pyramid[i+1]>>((j+1)*3)&7] {
pyramid[i] &^= 7 << (j * 3) // 清除之前填的字母，等价于 pyramid[i][j] = 0
pyramid[i] |= int(top) << (j * 3) // 等价于 pyramid[i][j] = top
if dfs(i, j+1) {
return true
}
}
return false
}

return dfs(n-2, 0)
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(|\Sigma|^n)$，其中 $n$ 是 $\textit{bottom}$ 的长度，$|\Sigma|=6$ 是字符集合的大小。
  • 空间复杂度：$\mathcal{O}(|\Sigma|^n)$。

专题训练

见下面回溯题单的「§4.7 搜索」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

一个可以炸掉目前几乎所有题解的测试用例，以及可以过的程序

✇LeetCode 每日一题题解
作者 ling-jian-2012
2021年8月2日 19:49
"ABBBBBBG"
["BDD","BFB","FDA","CCC","FBD","FBG","EEB","GBA","CFB","ECB","GDA","ECC","EFE","FCA","DBA","FAD","BEE","GEC","CFC","CFD","BCG","CAC","FCC","GAC","CAG","CFF","BEC","EAD","GBE","FEG","BDC","GBF","FBB","FBE","DDG","FDF","EDF","FAF","BEB","DDE","EEA","FAG","GDC","DFE","CDB","DFD","GDD","DAF","ECE","DBG","DDD","EFG","FAC","FEC","GED","DEE","CCF","EFD","FDE","GDF","ECG","DAE","FCG","DCA","EAF","EED","EEE","FEA","BFG","EAA","GDE","CEB","FAE","BDE","EBB","GFD","DBB","BFD","EFF","DAD","CDC","DCD","FFD","DBD","EFA","BCB","ECF","CFA","GFF","CFG","EEG","DAG","CAE","FED","CCA","EDE","FDG","BEF","FDD","BEG","FFE","DDC","BCE","GAA","GFE","FFF","CFE","BDF","DFG","DEF","FEF","GEE","EAB","GDB","CEE","BDA","DEG","DEC","GCG","DFB","EFB","GAB","CDF","CAF","BAB","GCC","DDA","CDD","FCB","DAA","GBG","BAC","GCE","GAG","EAE","EBG","GBD","BFE","CCD","EDD","FCD","FBC","DEB","EDG","GEA","EBE","GDG","DBE","BCD","GBB","FEB","DED","CAD","EDB","CED","GCD","BFC","GAE","CEG","EEC","FEE","GCA","FCF","ECD","DCC","BDB","EBD","DCE","BAE","FFG","DDF","DCF","BED","CAA","BCF","GBC","CCB","BCC","GFC","FFB","DFA","BBA","BBB","BBC","BBD","BBE","BBF","BBG","AAA","ABA","ACA","ADA","AEA","AFA","BGG","CGG","DGG","EGG","FGG","GGG"]

回溯法能过的唯一原因是数据太弱。

上面的测试用例的构造思路是这样的：形如A*的如AA,AB,AC...，但除AG以外，都只能放A，形如*G如BG,CG,...，但除AG以外，都只能放G。AG上没有能放的字母。其他组合上面能放几乎所有字母。

可以看出来对这个例子来说，每一层最左边只能是A，最右边只能是G，倒数第二层只能是AG，而AG上不能放字母，因此无解。但是所有的解都是在最后一步才失败的，因此遍历过的状态数极其巨大。

以官方题解为例，官方题解主要包括朴素的回溯和按行去重两种方法。朴素回溯的复杂度是O(A^(N^2))，而非题解说的O(A^N)，对于这个测试例来说，无论C++还是Java都会炸，Python就更不用说了。

按行去重也就是官方Java题解中用的方法，遇到整行的时候会缓存整行的结果，这可以将复杂度降至O(A^(2N))，差的这一点可以让Java通过（Java用位运算hash的方式常数也比较低），但是官方题解的Python即使打开seen的hash也会炸。

能通过的方法是将中途所有的状态都保存下来去重。每次尝试在下一层两个字母上堆一个字母的时候，下一层有一个字母就被压到底部了，它与后续求解无关，因此当前状态永远可以用上一层已经堆上的字母 + 下一层仍然露出来的字母来表示，总的状态数是O(NA^N)，正好在可以通过的范围内。

###python3

from functools import lru_cache


class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        trans = {}
        for p in allowed:
            trans.setdefault(p[:2], []).append(p[2])

        @lru_cache(None)
        def search(a, b):
            if len(a) == 2:
                if not b:
                    return a in trans
                else:
                    return any(search(b + t, '') for t in trans.get(a, []))
            else:
                return any(search(a[1:], b + t) for t in trans.get(a[:2], []))

        return search(bottom, '')

事实上这并不是最强的测试例，以下测试例耗时会更长：

"ADDDDDDA"
["ADA","ADB","ADC","AEA","AEB","AEC","AFA","AFB","AFC","AGA","AGB","AGC","BDA","BDB","BDC","BEA","BEB","BEC","BFA","BFB","BFC","BGA","BGB","BGC","CDA","CDB","CDC","CEA","CEB","CEC","CFA","CFB","CFC","CGA","CGB","CGC","DAA","DAB","DAC","DBA","DBB","DBC","DCA","DCB","DCC","EAA","EAB","EAC","EBA","EBB","EBC","ECA","ECB","ECC","FAA","FAB","FAC","FBA","FBB","FBC","FCA","FCB","FCC","GAA","GAB","GAC","GBA","GBB","GBC","GCA","GCB","GCC","DDA","DDB","DDC","DEA","DEB","DEC","DFA","DFB","DFC","DGA","DGB","DGC","EDA","EDB","EDC","EEA","EEB","EEC","EFA","EFB","EFC","EGA","EGB","EGC","FDA","FDB","FDC","FEA","FEB","FEC","FFA","FFB","FFC","FGA","FGB","FGC","GDA","GDB","GDC","GEA","GEB","GEC","GFA","GFB","GFC","GGA","GGB","GGC","DDD","DDE","DDF","DDG","DED","DEE","DEF","DEG","DFD","DFE","DFF","DFG","DGD","DGE","DGF","DGG","EDD","EDE","EDF","EDG","EED","EEE","EEF","EEG","EFD","EFE","EFF","EFG","EGD","EGE","EGF","EGG","FDD","FDE","FDF","FDG","FED","FEE","FEF","FEG","FFD","FFE","FFF","FFG","FGD","FGE","FGF","FGG","GDD","GDE","GDF","GDG","GED","GEE","GEF","GEG","GFD","GFE","GFF","GFG","GGD","GGE","GGF","GGG"]

"ADDDDDDA"
["GDF","EFB","FFC","DCB","GFD","GCD","BGA","EEC","DEC","EDD","CDA","FEF","CGD","ECA","DGD","FFD","BEA","GEE","EDE","CED","GEF","BCA","CFB","GGA","GGB","FDE","FGE","GAB","FBA","FFA","ECF","FDA","CCD","CGA","DED","EBB","FFG","BFB","FCB","DGE","DDB","BEB","GDG","FDB","FFB","CGB","GFE","FEG","FDC","CDF","GCE","DFD","DFG","CCA","GFA","FCE","BDA","ACA","CDB","GDE","EEA","FBB","FEC","DCA","FAB","CCE","GGF","CAA","EEF","CDD","FGA","DDC","CGC","DFF","CEE","EDC","FCA","GBB","CEC","DEE","DEB","AFB","EEG","FGB","FCD","GFC","GCA","DDD","FGC","ECC","FDF","GEC","DBB","DFB","EED","GAA","FGD","DBA","DCD","EBA","FCF","ECG","CDE","DCE","EAA","DAB","FDD","DFC","GGD","BGB","CBA","GDC","AGB","BFA","EFD","EGA","FAA","GEG","EAB","EDA","DEA","CEA","DCC","GCG","DAA","ECD","GFB","GBA","GCF","EEE","AFA","EGC","AGA","FEB","CCF","DGA","FFF","CCB","DDA","BCB","ADA","ECB","DGG","EGE","CFC","GCC","FGF","FDG","CGF","DDE","AEB","GGG","CCC","DCG","DDG","CEF","FGG","ACB","DFE","BDB","CCG","CGG","CFG","DGC","EFC","GDB","FEE","EDB","CFF","EFF","FEA","EFE","GEA","CDC","EDF","CGE","CFA","GGC","DEG","FCC","FFE","CFD","EDG","CAB","CEB","GDA","EGB","ECE","GCB","DGF","DGB","EGF","EGG","CEG","GFG","ADB","EFA","GFF","DEF","GEB"]

"AGGGGGGA"
["AFA","AFB","AFC","AFD","AFE","AGA","AGB","AGC","AGD","AGE","BFA","BFB","BFC","BFD","BFE","BGA","BGB","BGC","BGD","BGE","CFA","CFB","CFC","CFD","CFE","CGA","CGB","CGC","CGD","CGE","DFA","DFB","DFC","DFD","DFE","DGA","DGB","DGC","DGD","DGE","EFA","EFB","EFC","EFD","EFE","EGA","EGB","EGC","EGD","EGE","FAA","FAB","FAC","FAD","FAE","FBA","FBB","FBC","FBD","FBE","FCA","FCB","FCC","FCD","FCE","FDA","FDB","FDC","FDD","FDE","FEA","FEB","FEC","FED","FEE","GAA","GAB","GAC","GAD","GAE","GBA","GBB","GBC","GBD","GBE","GCA","GCB","GCC","GCD","GCE","GDA","GDB","GDC","GDD","GDE","GEA","GEB","GEC","GED","GEE","FFA","FFB","FFC","FFD","FFE","FGA","FGB","FGC","FGD","FGE","GFA","GFB","GFC","GFD","GFE","GGA","GGB","GGC","GGD","GGE","FFF","FFG","FGF","FGG","GFF","GFG","GGF","GGG"]

这两个测试例的构造思路是，将字母分成两类，一类是Type-0，一类是Type-1。0和0上不能放数字，0和1、1和0上只能放0类数字，而1和1上能放全部数字。然后给出的串两侧是Type-0字母，中间全部是Type-1字母。区别在于第一个使用ABC作为Type-0，第二个使用ABCD，第三个使用ABCDE。别看ABCDE时的allow数组似乎最短，但它对前面的算法威胁是最大的，因为最前面的测试例每一行两侧的字母固定是A和G，而这个例子中两侧的字母可以选择的数量更多，每一行中中间可以使用所有字母，两侧只能用Type-0，因此最后一个测试例的状态数是文章最开始测试例状态数的25倍。

这三个测试例可以炸掉LeetCode的标程，让标程超时（标程大概就是官方题解中记忆化的Java版本）。最后一个测试例可以炸掉上面的Python答案（如果改用Java或C++估计可以通过）。

在前面答案的基础上进行提前剪枝，可以减少状态数，通过这几个测试例：

###python3

from functools import lru_cache


class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        trans = {}
        for p in allowed:
            trans.setdefault(p[:2], []).append(p[2])

        @lru_cache(None)
        def search(a, b):
            if len(b) >= 2:
                if not search(b, ''):
                    return False
            if len(a) == 2:
                if not b:
                    return a in trans
                else:
                    return any(search(b + t, '') for t in trans.get(a, []))
            else:
                return any(search(a[1:], b + t) for t in trans.get(a[:2], []))

        return search(bottom, '')

注意到在处理(a,b)时，提前判断了(b,'')是否可行。这个判断对题目最开始的测试例没有太大帮助，但对后面这几个测试例有一定作用，主要是有效防止枚举出Type-0字符。目前没有已知的测试例可以fail这个程序了。

30行递递递递递递递递递递递递归

✇LeetCode 每日一题题解
作者 Eurka
2020年4月19日 14:41

解题思路

1.首先为allowed数组建立一个哈希表，键为下面的两块砖头，值为上面的砖头。注意，同样的下方砖头可能允许不同的上方砖头（例如ABC和ABD），故哈希表的值用vector。
2.递归函数gogogo接受三个参数，第一个bottom为目前检查的层，upper为已经形成的部分下一层，pos为目前bottom已经检查到了第几块砖头。
3.gogogo中，若pos == bottom.size()-1，说明这一层已经检查完毕啦，故将upper设为新的待检查层，注意哦，若upper.size()为1，说明已经到顶啦，返回true即可。
4.若下一个位置不存在可以放置的砖块，即vc.empty()，则返回false。否则，尝试所有可以放置的砖块。

代码

###cpp

class Solution {
public:
    unordered_map<string, vector<char>> mp;       
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for(string str:allowed){
            mp[str.substr(0, 2)].push_back(str.back());
        }
        string upper = "";
        return gogogo(bottom, upper, 0);
    }
    
    bool gogogo(string bottom, string upper, int pos){
        if(pos == bottom.size()-1){
            if(upper.size() == 1) return true;
            bottom = upper;
            upper = "";
            pos = 0;
        }
        vector<char>& vc= mp[bottom.substr(pos, 2)];
        if(vc.empty()) return false;
        else{
            for(int i = 0; i < vc.size(); i++){
                if(gogogo(bottom, upper + vc[i], pos+1)) return true;
            }
        }
        return false;
    }
};
昨天 — 2025年12月28日LeetCode 每日一题题解

每日一题-统计有序矩阵中的负数🟢

✇LeetCode 每日一题题解
2025年12月28日 00:00

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。 请你统计并返回 grid 中 负数 的数目。

 

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]
输出：0

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -100 <= grid[i][j] <= 100

 

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

【图解】疯狂撕数字，一图秒懂（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
作者 endlesscheng
2025年12月19日 19:41

lc1351-2c.png{:width=600px}

注：也可以从左下角开始，方法类似。

总结：利用 $\textit{grid}$ 行列有序的性质，我们可以用 $\mathcal{O}(1)$ 的时间获取 $\mathcal{O}(m)$ 或 $\mathcal{O}(n)$ 的信息。相比之下，$\mathcal{O}(mn)$ 的暴力查找（一个一个地找），每次花费 $\mathcal{O}(1)$ 的时间，只获取了 $\mathcal{O}(1)$ 的信息。

这就是为什么我们可以把 $\mathcal{O}(mn)$ 的暴力查找优化成 $\mathcal{O}(m+n)$。

###py

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        i, j = 0, n - 1  # 从右上角开始
        while i < m and j >= 0:  # 还有剩余元素
            if grid[i][j] < 0:
                ans += m - i  # 这一列剩余元素都是负数
                j -= 1
            else:
                i += 1  # 这一行剩余元素全都非负，排除
        return ans

###java

class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        int i = 0;
        int j = n - 1; // 从右上角开始
        while (i < m && j >= 0) { // 还有剩余元素
            if (grid[i][j] < 0) {
                ans += m - i; // 这一列剩余元素都是负数
                j--;
            } else {
                i++; // 这一行剩余元素全都非负，排除
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        int i = 0, j = n - 1; // 从右上角开始
        while (i < m && j >= 0) { // 还有剩余元素
            if (grid[i][j] < 0) {
                ans += m - i; // 这一列剩余元素都是负数
                j--;
            } else {
                i++; // 这一行剩余元素全都非负，排除
            }
        }
        return ans;
    }
};

###c

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    int ans = 0;
    int i = 0, j = n - 1; // 从右上角开始
    while (i < m && j >= 0) { // 还有剩余元素
        if (grid[i][j] < 0) {
            ans += m - i; // 这一列剩余元素都是负数
            j--;
        } else {
            i++; // 这一行剩余元素全都非负，排除
        }
    }
    return ans;
}

###go

func countNegatives(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
i, j := 0, n-1 // 从右上角开始
for i < m && j >= 0 { // 还有剩余元素
if grid[i][j] < 0 {
ans += m - i // 这一列剩余元素都是负数
j--
} else {
i++ // 这一行剩余元素全都非负，排除
}
}
return
}

###js

var countNegatives = function(grid) {
    const m = grid.length, n = grid[0].length;
    let ans = 0;
    let i = 0, j = n - 1; // 从右上角开始
    while (i < m && j >= 0) { // 还有剩余元素
        if (grid[i][j] < 0) {
            ans += m - i; // 这一列剩余元素都是负数
            j--;
        } else {
            i++; // 这一行剩余元素全都非负，排除
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = 0;
        let mut i = 0;
        let mut j = n - 1; // 从右上角开始
        while i < m && j < n { // 还有剩余元素
            if grid[i][j] < 0 {
                ans += m - i; // 这一列剩余元素都是负数
                j -= 1;
            } else {
                i += 1; // 这一行剩余元素全都非负，排除
            }
        }
        ans as _
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(m + n)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
  • 空间复杂度：$\mathcal{O}(1)$。

注：本题不存在时间复杂度低于 $\mathcal{O}(m + n)$ 的算法，见 240 题我的题解 文末的注。

相似题目

240. 搜索二维矩阵 II

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

两种解法，带图解

✇LeetCode 每日一题题解
作者 wan-dou-huang
2020年3月8日 10:37

解题思路

第一种：全部遍历，没什么技巧。
第二种：从右上到左下下梯子。
WeChat Image_20200308103704.jpg

代码

第一种：

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        total = 0
        for item in grid:
            for num in item:
                if num < 0 :
                    total += 1
        
        return total

第二种：

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        total = 0
        i, j = 0, len(grid[0])-1

        while i < len(grid) and j>=0:
            if grid[i][j] >= 0:
                i += 1
            else:
                total += len(grid) - i
                j -= 1
        return total

统计有序矩阵中的负数

✇LeetCode 每日一题题解
作者 LeetCode-Solution
2020年2月18日 20:22

方法一：暴力

观察数据范围注意到矩阵大小不会超过 $100*100=10^4$，所以我们可以遍历矩阵所有数，统计负数的个数。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        for (int x : grid) {
            for (int y : x) {
                if (y < 0) {
                    num++;
                }
            }
        }
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        for (int[] row : grid) {
            for (int value : row) {
                if (value < 0) {
                    num++;
                }
            }
        }
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        foreach (int[] row in grid) {
            foreach (int value in row) {
                if (value < 0) {
                    num++;
                }
            }
        }
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    for _, row := range grid {
        for _, value := range row {
            if value < 0 {
                num++
            }
        }
    }
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        for row in grid:
            for value in row:
                if value < 0:
                    num += 1
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            if (grid[i][j] < 0) {
                num++;
            }
        }
    }
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    for (const row of grid) {
        for (const value of row) {
            if (value < 0) {
                num++;
            }
        }
    }
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    for (const row of grid) {
        for (const value of row) {
            if (value < 0) {
                num++;
            }
        }
    }
    return num;
};

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        for row in grid {
            for value in row {
                if value < 0 {
                    num += 1;
                }
            }
        }
        num
    }
}

复杂度分析

  • 时间复杂度：$O(nm)$，即矩阵元素的总个数。
  • 空间复杂度：$O(1)$。

方法二：二分查找

注意到题目中给了一个性质，即矩阵中的元素无论是按行还是按列，都以非递增顺序排列，可以考虑把这个性质利用起来优化暴力。已知这个性质告诉了我们每一行的数都是有序的，所以我们通过二分查找可以找到每一行中从前往后的第一个负数，那么这个位置之后到这一行的末尾里所有的数必然是负数了，可以直接统计。

  1. 遍历矩阵的每一行。

  2. 二分查找到该行从前往后的第一个负数，考虑第 $i$ 行，我们记这个位置为 $pos_i$，那么第 $i$ 行 $[pos_i,m-1]$ 中的所有数都是负数，所以这一行对答案的贡献就是 $m-1-pos_i+1=m-pos_i$。

  3. 最后的答案就是 $\sum_{i=0}^{n-1}(m-pos_i)$。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        for (auto x : grid) {
            int l = 0, r = (int)x.size() - 1, pos = -1;
            while (l <= r) {
                int mid = l + ((r - l) >> 1);
                if (x[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            
            if (~pos) {  // pos != -1 表示这一行存在负数
                num += (int)x.size() - pos;
            }
        }
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        for (int[] row : grid) {
            int l = 0, r = row.length - 1, pos = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (row[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (pos != -1) {
                num += row.length - pos;
            }
        }
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        foreach (int[] row in grid) {
            int l = 0, r = row.Length - 1, pos = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (row[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (pos != -1) {
                num += row.Length - pos;
            }
        }
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    for _, row := range grid {
        l, r, pos := 0, len(row) - 1, -1
        for l <= r {
            mid := l + (r - l) / 2
            if row[mid] < 0 {
                pos = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        if pos != -1 {
            num += len(row) - pos
        }
    }
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        for row in grid:
            l, r, pos = 0, len(row) - 1, -1
            while l <= r:
                mid = l + (r - l) // 2
                if row[mid] < 0:
                    pos = mid
                    r = mid - 1
                else:
                    l = mid + 1
            if pos != -1:
                num += len(row) - pos
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    for (int i = 0; i < gridSize; i++) {
        int l = 0, r = gridColSize[i] - 1, pos = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (grid[i][mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos != -1) {
            num += gridColSize[i] - pos;
        }
    }
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    for (const row of grid) {
        let l = 0, r = row.length - 1, pos = -1;
        while (l <= r) {
            const mid = l + Math.floor((r - l) / 2);
            if (row[mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos !== -1) {
            num += row.length - pos;
        }
    }
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    for (const row of grid) {
        let l = 0, r = row.length - 1, pos = -1;
        while (l <= r) {
            const mid = l + Math.floor((r - l) / 2);
            if (row[mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos !== -1) {
            num += row.length - pos;
        }
    }
    return num;
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        for row in grid {
            let (mut l, mut r, mut pos) = (0, row.len() as i32 - 1, -1);
            while l <= r {
                let mid = l + (r - l) / 2;
                if row[mid as usize] < 0 {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if pos != -1 {
                num += row.len() as i32 - pos;
            }
        }
        num
    }
}

复杂度分析

  • 时间复杂度：二分查找一行的时间复杂度为$logm$，需要遍历$n$行，所以总时间复杂度是$O(nlogm)$。
  • 空间复杂度：$O(1)$。

方法三：分治

方法二其实只利用了一部分的性质，即每一行是非递增的，但其实整个矩阵是每行每列均非递增，这说明了一个更重要的性质：每一行从前往后第一个负数的位置是不断递减的，即我们设第 $i$ 行的第一个负数的位置为 $pos_i$，不失一般性，我们把一行全是正数的 $pos$ 设为 $m$，则
$$
pos_0>=pos_1>=pos_2>=...>=pos_{n-1}
$$
所以我们可以依此设计一个分治算法。

我们设计一个函数 $solve(l,r,L,R)$ 表示我们在统计 $[l,r]$ 行的答案，第 $[l,r]$ 行 $pos$ 的位置在 $[L,R]$ 列中，计算 $[l,r]$ 的中间行第 $mid$ 行的的 $pos_{mid}$，算完以后根据之前的方法计算这一行对答案的贡献。然后根据我们之前发现的性质，可以知道 $[l,mid-1]$ 中所有行的 $pos$ 是大于等于 $pos_{mid}$，$[mid+1,r]$ 中所有行的 $pos$ 值是小于等于 $pos_{mid}$ 的，所以可以分成两部分递归下去，即：
$$
solve(l,mid-1,pos_{mid},R)
$$
和
$$
solve(mid+1,r,L,pos_{mid})
$$
所以答案就是 $m-pos_{mid}+solve(l,mid-1,pos_{mid},R)+solve(mid+1,r,L,pos_{mid})$。

递归函数入口为 $solve(0,n-1,0,m-1)$。

###C++

class Solution {
public:
    int solve(int l, int r, int L, int R, vector<vector<int>>& grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + ((r - l) >> 1);
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; ++i) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += (int)grid[0].size() - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R, grid);
        }
        
        return ans;
    }
    
    int countNegatives(vector<vector<int>>& grid) {
        return solve(0, (int)grid.size() - 1, 0, (int)grid[0].size() - 1, grid);
    }
};

###Java

class Solution {
    private int solve(int l, int r, int L, int R, int[][] grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + (r - l) / 2;
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R, grid);
        }
        return ans;
    }
    
    public int countNegatives(int[][] grid) {
        return solve(0, grid.length - 1, 0, grid[0].length - 1, grid);
    }
}

###C#

public class Solution {
    private int Solve(int l, int r, int L, int R, int[][] grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + (r - l) / 2;
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].Length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += Solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += Solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += Solve(mid + 1, r, L, R, grid);
        }
        
        return ans;
    }
    
    public int CountNegatives(int[][] grid) {
        return Solve(0, grid.Length - 1, 0, grid[0].Length - 1, grid);
    }
}

###Go

func countNegatives(grid [][]int) int {
    var solve func(l, r, L, R int) int
    solve = func(l, r, L, R int) int {
        if l > r {
            return 0
        }
        
        mid := l + (r - l) / 2
        pos := -1
        // 在当前行中查找第一个负数
        for i := L; i <= R; i++ {
            if grid[mid][i] < 0 {
                pos = i
                break
            }
        }
        
        ans := 0
        if pos != -1 {
            // 当前行找到负数，计算当前行的负数个数
            ans += len(grid[0]) - pos
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid-1, pos, R)
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid+1, r, L, pos)
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid+1, r, L, R)
        }
        
        return ans
    }
    
    return solve(0, len(grid)-1, 0, len(grid[0])-1)
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        def solve(l: int, r: int, L: int, R: int) -> int:
            if l > r:
                return 0
            mid = l + (r - l) // 2
            pos = -1
            # 在当前行中查找第一个负数
            for i in range(L, R + 1):
                if grid[mid][i] < 0:
                    pos = i
                    break
            ans = 0
            if pos != -1:
                # 当前行找到负数，计算当前行的负数个数
                ans += len(grid[0]) - pos
                # 递归处理上半部分（使用更小的列范围）
                ans += solve(l, mid - 1, pos, R)
                # 递归处理下半部分（使用相同的列起始范围）
                ans += solve(mid + 1, r, L, pos)
            else:
                # 当前行没有负数，只需要递归处理下半部分
                ans += solve(mid + 1, r, L, R)

            return ans
            
        return solve(0, len(grid) - 1, 0, len(grid[0]) - 1)

###C

int solve(int l, int r, int L, int R, int** grid, int gridSize, int gridColSize) {
    if (l > r) {
        return 0;
    }
    
    int mid = l + (r - l) / 2;
    int pos = -1;
    // 在当前行中查找第一个负数
    for (int i = L; i <= R; i++) {
        if (grid[mid][i] < 0) {
            pos = i;
            break;
        }
    }
    
    int ans = 0;
    if (pos != -1) {
        // 当前行找到负数，计算当前行的负数个数
        ans += gridColSize - pos;
        // 递归处理上半部分（使用更小的列范围）
        ans += solve(l, mid - 1, pos, R, grid, gridSize, gridColSize);
        // 递归处理下半部分（使用相同的列起始范围）
        ans += solve(mid + 1, r, L, pos, grid, gridSize, gridColSize);
    } else {
        // 当前行没有负数，只需要递归处理下半部分
        ans += solve(mid + 1, r, L, R, grid, gridSize, gridColSize);
    }
    
    return ans;
}

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    return solve(0, gridSize - 1, 0, gridColSize[0] - 1, grid, gridSize, gridColSize[0]);
}

###JavaScript

var countNegatives = function(grid) {
    const solve = (l, r, L, R) => {
        if (l > r) {
            return 0;
        }
        
        const mid = l + Math.floor((r - l) / 2);
        let pos = -1;
        // 在当前行中查找第一个负数
        for (let i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        let ans = 0;
        if (pos !== -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R);
        }
        
        return ans;
    };
    
    return solve(0, grid.length - 1, 0, grid[0].length - 1);
};

###TypeScript

function countNegatives(grid: number[][]): number {
    const solve = (l: number, r: number, L: number, R: number): number => {
        if (l > r) {
            return 0;
        }
        
        const mid = l + Math.floor((r - l) / 2);
        let pos = -1;
        // 在当前行中查找第一个负数
        for (let i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        let ans = 0;
        if (pos !== -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R);
        }
        
        return ans;
    };
    
    return solve(0, grid.length - 1, 0, grid[0].length - 1);
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        fn solve(l: i32, r: i32, L: i32, R: i32, grid: &Vec<Vec<i32>>) -> i32 {
            if l > r {
                return 0;
            }
            
            let mid = l + (r - l) / 2;
            let mut pos = -1;
            // 在当前行中查找第一个负数
            for i in L..=R {
                if grid[mid as usize][i as usize] < 0 {
                    pos = i;
                    break;
                }
            }
            
            let mut ans = 0;
            if pos != -1 {
                // 当前行找到负数，计算当前行的负数个数
                ans += grid[0].len() as i32 - pos;
                // 递归处理上半部分（使用更小的列范围）
                ans += solve(l, mid - 1, pos, R, grid);
                // 递归处理下半部分（使用相同的列起始范围）
                ans += solve(mid + 1, r, L, pos, grid);
            } else {
                // 当前行没有负数，只需要递归处理下半部分
                ans += solve(mid + 1, r, L, R, grid);
            }
            
            ans
        }
        
        solve(0, grid.len() as i32 - 1, 0, grid[0].len() as i32 - 1, &grid)
    }
}

复杂度分析

  • 时间复杂度：代码中找第一个负数的位置是直接遍历 $[L,R]$ 找的，再考虑到 $n$ 和 $m$ 同阶，所以每个 $solve$ 函数里需要消耗 $O(n)$ 的时间，由主定理可得时间复杂度为：
    $$
    T(n)=2T(n/2)+O(n)=O(nlogn)
    $$

  • 空间复杂度：$O(1)$。

方法四：倒序遍历

考虑方法三发现的性质，我们可以设计一个更简单的方法。考虑我们已经算出第 $i$ 行的从前往后第一个负数的位置 $pos_i$，那么第 $i+1$ 行的时候，$pos_{i+1}$ 的位置肯定是位于 $[0,pos_i]$ 中，所以对于第 $i+1$ 行我们倒着从 $pos_i$ 循环找 $pos_{i+1}$ 即可，这个循环起始变量是一直在递减的。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        int m = (int)grid[0].size();
        int pos = (int)grid[0].size() - 1;
        
        for (auto& row : grid) {
            int i;
            for (i = pos; i >= 0; --i) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        int m = grid[0].length;
        int pos = grid[0].length - 1;
        
        for (int[] row : grid) {
            int i;
            for (i = pos; i >= 0; i--) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        int m = grid[0].Length;
        int pos = grid[0].Length - 1;
        
        foreach (int[] row in grid) {
            int i;
            for (i = pos; i >= 0; i--) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    m := len(grid[0])
    pos := len(grid[0]) - 1
    
    for _, row := range grid {
        i := pos
        for ; i >= 0; i-- {
            if row[i] >= 0 {
                if i + 1 < m {
                    pos = i + 1
                    num += m - pos
                }
                break
            }
        }
        if i == -1 {
            num += m
            pos = -1
        }
    }
    
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        m = len(grid[0])
        pos = len(grid[0]) - 1
        
        for row in grid:
            i = pos
            while i >= 0:
                if row[i] >= 0:
                    if i + 1 < m:
                        pos = i + 1
                        num += m - pos
                    break
                i -= 1
            if i == -1:
                num += m
                pos = -1
        
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    int m = gridColSize[0];
    int pos = gridColSize[0] - 1;
    
    for (int i = 0; i < gridSize; i++) {
        int j;
        for (j = pos; j >= 0; j--) {
            if (grid[i][j] >= 0) {
                if (j + 1 < m) {
                    pos = j + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (j == -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    const m = grid[0].length;
    let pos = grid[0].length - 1;
    
    for (const row of grid) {
        let i;
        for (i = pos; i >= 0; i--) {
            if (row[i] >= 0) {
                if (i + 1 < m) {
                    pos = i + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (i === -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    const m = grid[0].length;
    let pos = grid[0].length - 1;
    
    for (const row of grid) {
        let i: number;
        for (i = pos; i >= 0; i--) {
            if (row[i] >= 0) {
                if (i + 1 < m) {
                    pos = i + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (i === -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        let m = grid[0].len();
        let mut pos = (grid[0].len() - 1) as i32;
        
        for row in grid {
            let mut i = pos;
            while i >= 0 {
                if row[i as usize] >= 0 {
                    if i + 1 < m as i32 {
                        pos = i + 1;
                        num += (m as i32) - pos;
                    }
                    break;
                }
                i -= 1;
            }
            if i == -1 {
                num += m as i32;
                pos = -1;
            }
        }
        
        num
    }
}

复杂度分析

  • 时间复杂度：考虑每次循环变量的起始位置是单调不降的，所以起始位置最多移动 $m$ 次，时间复杂度 $O(n+m)$。
  • 空间复杂度：$O(1)$。
昨天以前LeetCode 每日一题题解

每日一题-会议室 III🔴

✇LeetCode 每日一题题解
2025年12月27日 00:00

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

  1. 每场会议都会在未占用且编号 最小 的会议室举办。
  2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
  3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。

 

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。

 

提示：

  • 1 <= n <= 100
  • 1 <= meetings.length <= 105
  • meetings[i].length == 2
  • 0 <= starti < endi <= 5 * 105
  • starti 的所有值 互不相同

n<=100，代码可以写得简单（比赛时想复杂了）

✇LeetCode 每日一题题解
作者 newhar
2022年9月4日 12:21

由于 $n\le 100$，可以直接按照题目模拟：

  1. 按开始时间排序，依次安排 meetings

  2. 维护每个会议室的 最早可用时间 $t$。每次安排会议$[start, end)$时，将那些 $t$ 早于 $start$ 的会议室的 $t$ 设为 $start$。这样处理后只需从中选择 $t$ 最早的会议室即可（如果有相等的选下标最小的）。

  3. 同时维护 $cnt$ 数组，遍历完成后按要求返回答案即可

###python

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        cnt, t = [0] * n, [0] * n
        
        for [s, e] in sorted(meetings):
            t = list(map(lambda x : max(x, s), t))
            choice = t.index(min(t))
            t[choice], cnt[choice] = t[choice] + e - s, cnt[choice] + 1
            
        return cnt.index(max(cnt))

双堆模拟（Python/Java/C++/Go）

✇LeetCode 每日一题题解
作者 endlesscheng
2022年9月4日 12:07

按照时间顺序模拟开会过程。

对于会议 $[\textit{start},\textit{end})$，我们需要知道：

  • 在 $\textit{start}$ 时刻空闲的会议室中，编号最小的会议室。可以用一个最小堆 $\textit{idle}$ 维护空闲会议室的编号。
  • 如果没有空闲的会议室呢？我们需要找最早结束的会议室。可以用一个最小堆 $\textit{using}$ 维护使用中的会议室的结束时间和编号。

这两类会议室是互补关系，伴随着会议的开始和结束，会议室在这两类中来回倒：

  • 首先，从 $\textit{using}$ 中去掉结束时间小于等于 $\textit{start}$ 的所有会议室，将其编号添加到 $\textit{idle}$ 中。
  • 然后分类讨论：
    • 如果此时有空闲的会议室，那么从 $\textit{idle}$ 中弹出编号最小的会议室，和 $\textit{end}$ 一起，添加到 $\textit{using}$ 中。
    • 否则，从 $\textit{using}$ 中弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室），设其结束时间为 $e$，则我们等待了 $e-\textit{start}$ 时间，所以当前会议的结束时间为 $\textit{end} + e-\textit{start}$。

在上述模拟的过程中，每使用一个编号为 $i$ 的会议室，就把 $i$ 的出现次数加一。最后返回出现次数最大的编号（如果有多个编号的出现次数相同，返回其中最小的编号）。

注意题目保证所有会议的开始时间互不相同。

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort(key=lambda m: m[0])

        idle = list(range(n))  # 会议室编号
        using = []  # (结束时间，会议室编号)
        cnt = [0] * n  # 会议室的开会次数

        for start, end in meetings:
            # 在 start 时刻空出来的会议室
            while using and using[0][0] <= start:
                heappush(idle, heappop(using)[1])

            if idle:  # 有空闲的会议室
                i = heappop(idle)
            else:  # 没有空闲的会议室
                e, i = heappop(using)  # 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                end += e - start  # 更新当前会议的结束时间

            heappush(using, (end, i))  # 使用一个会议室
            cnt[i] += 1

        return cnt.index(max(cnt))

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> idle = new PriorityQueue<>(); // 会议室编号
        for (int i = 0; i < n; i++) {
            idle.offer(i);
        }
        PriorityQueue<long[]> using = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])
        ); // (结束时间，会议室编号)
        int[] cnt = new int[n]; // 会议室的开会次数

        for (int[] m : meetings) {
            long start = m[0];
            long end = m[1];

            // 在 start 时刻空出来的会议室
            while (!using.isEmpty() && using.peek()[0] <= start) {
                idle.offer((int) using.poll()[1]);
            }

            int i;
            if (!idle.isEmpty()) { // 有空闲的会议室
                i = idle.poll();
            } else { // 没有空闲的会议室
                long[] p = using.poll(); // 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                end += p[0] - start; // 更新当前会议的结束时间
                i = (int) p[1];
            }

            using.offer(new long[]{end, i}); // 使用一个会议室
            cnt[i]++;
        }

        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (cnt[i] > cnt[ans]) {
                ans = i;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        ranges::sort(meetings, {}, [](auto& m) { return m[0]; });

        priority_queue<int, vector<int>, greater<>> idle; // 会议室编号
        for (int i = 0; i < n; i++) {
            idle.push(i);
        }
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> using_; // (结束时间，会议室编号)
        vector<int> cnt(n); // 会议室的开会次数

        for (auto& m : meetings) {
            long long start = m[0], end = m[1];

            // 在 start 时刻空出来的会议室
            while (!using_.empty() && using_.top().first <= start) {
                idle.push(using_.top().second);
                using_.pop();
            }

            int i;
            if (!idle.empty()) { // 有空闲的会议室
                i = idle.top();
                idle.pop();
            } else { // 没有空闲的会议室
                // 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
                auto [e, room] = using_.top();
                i = room;
                using_.pop(); 
                end += e - start; // 更新当前会议的结束时间
            }

            using_.emplace(end, i); // 使用一个会议室
            cnt[i]++;
        }

        return ranges::max_element(cnt) - cnt.begin();
    }
};

func mostBooked(n int, meetings [][]int) (ans int) {
slices.SortFunc(meetings, func(a, b []int) int { return a[0] - b[0] })

idle := hp{make([]int, n)} // 会议室编号
for i := range n {
idle.IntSlice[i] = i
}
using := hp2{} // (结束时间，会议室编号)
cnt := make([]int, n) // 会议室的开会次数

for _, m := range meetings {
start, end := m[0], m[1]

// 在 start 时刻空出来的会议室
for len(using) > 0 && using[0].end <= start {
heap.Push(&idle, heap.Pop(&using).(pair).i)
}

var i int
if idle.Len() > 0 { // 有空闲的会议室
i = heap.Pop(&idle).(int)
} else {
// 弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室）
p := heap.Pop(&using).(pair)
end += p.end - start // 更新当前会议的结束时间  
i = p.i
}

heap.Push(&using, pair{end, i}) // 使用一个会议室
cnt[i]++
}

for i, c := range cnt {
if c > cnt[ans] {
ans = i
}
}
return
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

type pair struct{ end, i int }
type hp2 []pair
func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool {
a, b := h[i], h[j]
return a.end < b.end || a.end == b.end && a.i < b.i
}
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any)   { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any     { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

复杂度分析

  • 时间复杂度：$\mathcal{O}(m\log m + n + m\log n)$，其中 $m$ 是 $\textit{meetings}$ 的长度。注意每个会议至多入堆出堆各一次。
  • 空间复杂度：$\mathcal{O}(n)$。

相似题目

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

模拟

✇LeetCode 每日一题题解
作者 tsreaper
2022年9月4日 12:07

解法：模拟

因为“当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议”，因此有重要性质：会议开始的相对顺序不会改变。我们只需要按顺序模拟每个会议分配给哪个会议室即可。

复杂度 $\mathcal{O}(m\log m + nm)$，其中 $m$ 是会议的数量。具体实现见参考代码，注意会议的结束时间可能超出 int 的范围。

参考代码（c++）

###c++

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        int m = meetings.size();
        // 将会议按开始时间排序
        sort(meetings.begin(), meetings.end());
        // 每个会议室被分配了多少会议
        vector<int> cnt(n);
        // 每个会议室的最早可用时间
        vector<long long> tim(n);
        // 按顺序处理会议
        for (auto &meet : meetings) {
            // best 表示当前不可用，但可用时间最早的会议室编号
            int best = 0;
            for (int i = 0; i < n; i++) {
                if (tim[i] <= meet[0]) {
                    // 当前会议室可用，直接分配
                    cnt[i]++;
                    tim[i] = meet[1];
                    goto OK;
                } else if (tim[i] < tim[best]) best = i; // 当前会议室不可用，更新 best
            }
            // 当前没有会议室可用，等待会议室 best 可用再分配
            cnt[best]++;
            tim[best] += meet[1] - meet[0];
            OK: continue;
        }
        // 统计答案
        int ans = 0;
        for (int i = 0; i < n; i++) if (cnt[i] > cnt[ans]) ans = i;
        return ans;
    }
};

也可以使用线段树将复杂度降至 $\mathcal{O}(m\log m + m\log n)$。

参考代码（c++）

###c++

class Solution {
    vector<long long> mino;

    // 修改 pos 位置的值为 val
    void modify(int id, int l, int r, int pos, long long val) {
        if (l == r) mino[id] = val;
        else {
            int nxt = id << 1, mid = (l + r) >> 1;
            if (pos <= mid) modify(nxt, l, mid, pos, val);
            else modify(nxt | 1, mid + 1, r, pos, val);
            mino[id] = min(mino[nxt], mino[nxt | 1]);
        }
    }

    // 求编号最小的，且值小等于 val 的位置
    int query1(int id, int l, int r, int val) {
        if (l == r) return l;
        else {
            int nxt = id << 1, mid = (l + r) >> 1;
            if (mino[id] > val) return -1;
            else if (mino[nxt] <= val) return query1(nxt, l, mid, val);
            else return query1(nxt | 1, mid + 1, r, val);
        }
    }

    // 求值最小的位置在哪里
    int query2(int id, int l, int r) {
        if (l == r) return l;
        else {
            int nxt = id << 1, mid = (l + r) >> 1;
            return mino[nxt] <= mino[nxt | 1] ? query2(nxt, l, mid) : query2(nxt | 1, mid + 1, r);
        }
    }

public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        mino.resize(n * 4 + 10);
        int m = meetings.size();
        sort(meetings.begin(), meetings.end());

        vector<int> cnt(n);
        for (auto &meet : meetings) {
            // 是否直接有会议室可用
            int x = query1(1, 0, n - 1, meet[0]);
            if (x >= 0) cnt[x]++, modify(1, 0, n - 1, x, meet[1]); // 直接有会议室可用，更新该会议室的可用时间
            else {
                // 没有会议室直接可用，找接下来最早可用的会议室
                x = query2(1, 0, n - 1);
                // 更新该会议室的可用时间
                cnt[x]++;
                modify(1, 0, n - 1, x, mino[1] + meet[1] - meet[0]);
            }
        }

        // 统计答案
        int ans = 0;
        for (int i = 0; i < n; i++) if (cnt[i] > cnt[ans]) ans = i;
        return ans;
    }
};

每日一题-商店的最少代价🟡

✇LeetCode 每日一题题解
2025年12月26日 00:00

给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示：

  • 如果第 i 个字符是 'Y' ，它表示第 i 小时有顾客到达。
  • 如果第 i 个字符是 'N' ，它表示第 i 小时没有顾客到达。

如果商店在第 j 小时关门（0 <= j <= n），代价按如下方式计算：

  • 在开门期间，如果某一个小时没有顾客到达，代价增加 1 。
  • 在关门期间，如果某一个小时有顾客到达，代价增加 1 。

请你返回在确保代价 最小 的前提下，商店的 最早 关门时间。

注意，商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。

 

示例 1：

输入：customers = "YYNY"
输出：2
解释：
- 第 0 小时关门，总共 1+1+0+1 = 3 代价。
- 第 1 小时关门，总共 0+1+0+1 = 2 代价。
- 第 2 小时关门，总共 0+0+0+1 = 1 代价。
- 第 3 小时关门，总共 0+0+1+1 = 2 代价。
- 第 4 小时关门，总共 0+0+1+0 = 1 代价。
在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早，所以最优关门时间是 2 。

示例 2：

输入：customers = "NNNNN"
输出：0
解释：最优关门时间是 0 ，因为自始至终没有顾客到达。

示例 3：

输入：customers = "YYYY"
输出：4
解释：最优关门时间是 4 ，因为每一小时均有顾客到达。

 

提示：

  • 1 <= customers.length <= 105
  • customers 只包含字符 'Y' 和 'N' 。

[Java] 前缀和 & 空间优化

✇LeetCode 每日一题题解
作者 Tizzi
2022年11月29日 11:18

解法一：前缀和

利用前缀和，后缀和统计N，Y的数字即可，最后计算出最小的答案。

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$
class Solution {
    public int bestClosingTime(String cus) {
        int n = cus.length(), maxv = 100005, ans = 0;
        char[] arr = cus.toCharArray();
        int[] left = new int[n + 5], right = new int[n + 5];
        for (int i = 1; i <= n; i++) left[i] += left[i - 1] + (arr[i - 1] == 'N' ? 1 : 0);
        for (int i = n; i >= 1; i--) right[i] += right[i + 1] + (arr[i - 1] == 'Y' ? 1 : 0);
        for (int i = 1; i <= n + 1; i++) {
            if (left[i - 1] + right[i] < maxv) {
                maxv = left[i - 1] + right[i];
                ans = i - 1;
            }
        }
        return ans;
    }
}

解法二：空间优化

先统计所有Y的个数，然后对于当前字符计算代价即可，最后更新总代价。

class Solution {
    public int bestClosingTime(String cus) {
        int n = cus.length(), maxv = 100005, ans = 0;
        char[] arr = cus.toCharArray();
        int left_right = 0; 
        for (int i = n; i >= 1; i--) left_right += (arr[i - 1] == 'Y' ? 1 : 0);
        for (int i = 1; i <= n + 1; i++) {
            if (left_right < maxv) {
                maxv = left_right;
                ans = i - 1;
            }
            if (i <= n && arr[i - 1] == 'Y') left_right--;
            else left_right++;
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

如果有问题,欢迎评论区交流, 如果有帮助到你，请给题解点个赞和收藏哈~~~

前后缀分解，一次遍历优化（Python/Java/C++/Go）

✇LeetCode 每日一题题解
作者 endlesscheng
2022年11月27日 09:02

题意

把 $\textit{customers}$ 分成两段，第一段计算 $\texttt{N}$ 的个数 $\textit{preN}$，第二段计算 $\texttt{Y}$ 的个数 $\textit{sufY}$。

计算 $\textit{preN}+\textit{sufY}$ 的最小值对应的最小分割位置 $i$，其中 $[0,i-1]$ 是第一段，$[i,n-1]$ 是第二段。

注：也可以不分割，相当于其中一段是空的。

思路

先假设所有字母都在第二段，统计 $\textit{customers}$ 中 $\texttt{Y}$ 的个数 $\textit{sufY}$。

想象一根分割线在从左到右移动，$\textit{customers}[i]$ 原来在第二段，现在在第一段。如果 $\textit{customers}[i] = \texttt{N}$，那么把 $\textit{preN}$ 加一（$\textit{preN}$ 初始值为 $0$），否则把 $\textit{sufY}$ 减一。

答案为 $\textit{preN}+\textit{sufY}$ 最小时对应的分割位置。

代码实现时，$\textit{preN}+\textit{sufY}$ 可以合并为一个变量 $\textit{penalty}$。

优化前

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        min_penalty = penalty = customers.count('Y')
        ans = 0  # [0,n-1] 是第二段
        for i, c in enumerate(customers):
            penalty += 1 if c == 'N' else -1
            if penalty < min_penalty:
                min_penalty = penalty
                ans = i + 1  # [0,i] 是第一段，[i+1,n-1] 是第二段
        return ans

class Solution {
    public int bestClosingTime(String customers) {
        char[] s = customers.toCharArray();
        int penalty = 0;
        for (char c : s) {
            if (c == 'Y') {
                penalty++;
            }
        }

        int minPenalty = penalty;
        int ans = 0; // [0,n-1] 是第二段
        for (int i = 0; i < s.length; i++) {
            penalty += s[i] == 'N' ? 1 : -1;
            if (penalty < minPenalty) {
                minPenalty = penalty;
                ans = i + 1; // [0,i] 是第一段，[i+1,n-1] 是第二段
            }
        }
        return ans;
    }
}

class Solution {
public:
    int bestClosingTime(string customers) {
        int penalty = ranges::count(customers, 'Y');
        int min_penalty = penalty;
        int ans = 0; // [0,n-1] 是第二段
        for (int i = 0; i < customers.size(); i++) {
            penalty += customers[i] == 'N' ? 1 : -1;
            if (penalty < min_penalty) {
                min_penalty = penalty;
                ans = i + 1; // [0,i] 是第一段，[i+1,n-1] 是第二段
            }
        }
        return ans;
    }
};

func bestClosingTime(customers string) int {
penalty := strings.Count(customers, "Y")
minPenalty := penalty
ans := 0 // [0,n-1] 是第二段
for i, c := range customers {
if c == 'N' {
penalty++
} else {
penalty--
}
if penalty < minPenalty {
minPenalty = penalty
ans = i + 1 // [0,i] 是第一段，[i+1,n-1] 是第二段
}
}
return ans
}

优化：一次遍历

第一次遍历（统计 $\texttt{Y}$ 的个数）是多余的。

打个比方，绝对温度下冰点为 $273,\mathrm{K}$，摄氏温度下冰点为 $0~^\circ\mathrm{C}$。如果只关心哪一天最冷，用哪个单位计算都可以。

或者说，把折线图往下平移（第一个点移到坐标零点），最低点的横坐标仍然不变。

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        min_penalty = penalty = ans = 0
        for i, c in enumerate(customers):
            penalty += 1 if c == 'N' else -1
            if penalty < min_penalty:
                min_penalty = penalty
                ans = i + 1
        return ans

class Solution {
    public int bestClosingTime(String customers) {
        int penalty = 0;
        int minPenalty = 0;
        int ans = 0;
        for (int i = 0; i < customers.length(); i++) {
            penalty += customers.charAt(i) == 'N' ? 1 : -1;
            if (penalty < minPenalty) {
                minPenalty = penalty;
                ans = i + 1;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int bestClosingTime(string customers) {
        int penalty = 0, min_penalty = 0, ans = 0;
        for (int i = 0; i < customers.size(); i++) {
            penalty += customers[i] == 'N' ? 1 : -1;
            if (penalty < min_penalty) {
                min_penalty = penalty;
                ans = i + 1;
            }
        }
        return ans;
    }
};

func bestClosingTime(customers string) (ans int) {
penalty, minPenalty := 0, 0
for i, c := range customers {
if c == 'N' {
penalty++
} else {
penalty--
}
if penalty < minPenalty {
minPenalty = penalty
ans = i + 1
}
}
return
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{customers}$ 的长度。
  • 空间复杂度：$\mathcal{O}(1)$。

相似题目

3694. 删除子字符串后不同的终点

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

枚举 & 前缀和

✇LeetCode 每日一题题解
作者 tsreaper
2022年11月27日 00:09

解法：枚举 & 前缀和

为了方便计算前（后）缀和，我们认为 customers 的下标是从 $1$ 开始的，最后答案减 $1$ 即可。

维护 $f(i)$ 表示第 $1$ 到第 $i$ 个字符有几个 N（初值 $f(0) = 0$），$g(i)$ 表示第 $i$ 到第 $n$ 个字符有几个 Y（初值 $g(n + 1) = 0$），那么第 $h$ 小时关店的代价即为 $f(h - 1) + g(h)$。

从 $1$ 到 $(n + 1)$ 枚举所有 $h$ 并选出代价最小的即可。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###c++

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();

        int f[n + 2], g[n + 2];
        // 计算前缀有几个 N
        f[0] = 0;
        for (int i = 1; i <= n; i++) f[i] = f[i - 1] + (customers[i - 1] == 'N' ? 1 : 0);
        // 计算后缀有几个 Y
        g[n + 1] = 0;
        for (int i = n; i > 0; i--) g[i] = g[i + 1] + (customers[i - 1] == 'Y' ? 1 : 0);

        // 枚举答案
        int ans = 0, best = 1e9;
        for (int i = 1; i <= n + 1; i++) {
            int tmp = f[i - 1] + g[i];
            if (tmp < best) ans = i, best = tmp;
        }
        return ans - 1;
    }
};

[Python3/Java/C++/Go/TypeScript] 一题一解：贪心 + 排序（清晰题解）

✇LeetCode 每日一题题解
作者 lcbin
2025年12月25日 07:33

方法一：贪心 + 排序

为了使得幸福值之和尽可能大，我们应该优先选择幸福值大的孩子。因此，我们可以对孩子按照幸福值从大到小排序，然后依次选择 $k$ 个孩子。对于当前第 $i$ 个孩子，能够得到的幸福值为 $\max(\textit{happiness}[i] - i, 0)$，最后返回这 $k$ 个孩子的幸福值之和。

###python

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(reverse=True)
        ans = 0
        for i, x in enumerate(happiness[:k]):
            x -= i
            ans += max(x, 0)
        return ans

###java

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        long ans = 0;
        for (int i = 0, n = happiness.length; i < k; ++i) {
            int x = happiness[n - i - 1] - i;
            ans += Math.max(x, 0);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.rbegin(), happiness.rend());
        long long ans = 0;
        for (int i = 0, n = happiness.size(); i < k; ++i) {
            int x = happiness[i] - i;
            ans += max(x, 0);
        }
        return ans;
    }
};

###go

func maximumHappinessSum(happiness []int, k int) (ans int64) {
sort.Ints(happiness)
for i := 0; i < k; i++ {
x := happiness[len(happiness)-i-1] - i
ans += int64(max(x, 0))
}
return
}

###ts

function maximumHappinessSum(happiness: number[], k: number): number {
    happiness.sort((a, b) => b - a);
    let ans = 0;
    for (let i = 0; i < k; ++i) {
        const x = happiness[i] - i;
        ans += Math.max(x, 0);
    }
    return ans;
}

###rust

impl Solution {
    pub fn maximum_happiness_sum(mut happiness: Vec<i32>, k: i32) -> i64 {
        happiness.sort_unstable_by(|a, b| b.cmp(a));

        let mut ans: i64 = 0;
        for i in 0..(k as usize) {
            let x = happiness[i] as i64 - i as i64;
            if x > 0 {
                ans += x;
            }
        }
        ans
    }
}

###cs

public class Solution {
    public long MaximumHappinessSum(int[] happiness, int k) {
        Array.Sort(happiness, (a, b) => b.CompareTo(a));
        long ans = 0;
        for (int i = 0; i < k; i++) {
            int x = happiness[i] - i;
            if (x <= 0) {
                break;
            }
            ans += x;
        }
        return ans;
    }
}

时间复杂度 $O(n \times \log n + k)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $\textit{happiness}$ 的长度。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

每日一题-幸福值最大化的选择方案🟡

✇LeetCode 每日一题题解
2025年12月25日 00:00

给你一个长度为 n 的数组 happiness ，以及一个 正整数 k 。

n 个孩子站成一队，其中第 i 个孩子的 幸福值 是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。

在每一轮选择一个孩子时，所有 尚未 被选中的孩子的 幸福值 将减少 1 。注意，幸福值 不能 变成负数，且只有在它是正数的情况下才会减少。

选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。

 

示例 1：

输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。

示例 2：

输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
所选孩子的幸福值之和为 1 + 0 = 1 。

示例 3：

输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
所选孩子的幸福值之和为 5 。

 

提示：

  • 1 <= n == happiness.length <= 2 * 105
  • 1 <= happiness[i] <= 108
  • 1 <= k <= n
❌
❌