给你一个 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.lengthn == grid[i].length1 <= m, n <= 100-100 <= grid[i][j] <= 100
进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？
{: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)$ 的算法，见 240 题我的题解 文末的注。
欢迎关注 B站@灵茶山艾府
第一种：全部遍历，没什么技巧。
第二种：从右上到左下下梯子。
第一种：
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
观察数据范围注意到矩阵大小不会超过 $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
}
}
复杂度分析
注意到题目中给了一个性质，即矩阵中的元素无论是按行还是按列，都以非递增顺序排列，可以考虑把这个性质利用起来优化暴力。已知这个性质告诉了我们每一行的数都是有序的，所以我们通过二分查找可以找到每一行中从前往后的第一个负数，那么这个位置之后到这一行的末尾里所有的数必然是负数了，可以直接统计。
遍历矩阵的每一行。
二分查找到该行从前往后的第一个负数，考虑第 $i$ 行，我们记这个位置为 $pos_i$，那么第 $i$ 行 $[pos_i,m-1]$ 中的所有数都是负数，所以这一行对答案的贡献就是 $m-1-pos_i+1=m-pos_i$。
最后的答案就是 $\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
}
}
复杂度分析
方法二其实只利用了一部分的性质，即每一行是非递增的，但其实整个矩阵是每行每列均非递增，这说明了一个更重要的性质：每一行从前往后第一个负数的位置是不断递减的，即我们设第 $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
}
}
复杂度分析
核心对象：
生命周期：
整个过程分为【初始化->编译->输出->结束】，一共四个阶段，以下列举一下各个阶段的核心钩子：
compiler.hooks.compiler.tap('插件名',()=>{
compiler.options.plugins.push(
new webpack.DefinePlugin({
'process.env.APP_VERSION': JSON.stringify(PLACEHOLDER),
})
);
console.log('✅ 已注入APP_VERSION占位符：', PLACEHOLDER);
})
compiler.hooks.compilation.tap('ContentHashReplacePlugin', () => {
this.contentHash = this.generateContentHash();
console.log('✅ 生成真实contentHash：', this.contentHash);
});
compiler.hooks.emit.tapAsync('MyPlugin', (compilation, callback) => {
// 遍历所有输出的资源
for (const [filename, source] of Object.entries(compilation.assets)) {
if (filename.endsWith('.js')) {
// 读取原内容，添加版权注释
const content = source.source();
const newContent = `/* 版权所有 © 2025 MyProject */\n${content}`;
// 替换资源内容
compilation.assets[filename] = {
source: () => newContent,
size: () => newContent.length
};
}
}
callback(); // 异步钩子必须调用 callback 结束
});
tap和tapAsync的区别:
同步钩子和异步钩子调用时候的函数。
tapAsync必须和callback结合使用，用于通知webpack异步流程已经结束，可以继续接下来的流程，不然会卡住。
Plugin: 用于webpack打包生命周期中执行的一些函数，比如css和图片压缩的plugin，无视打包模块的IgnorePlugin
Loader: 用于代码转换，因为浏览器只能解析html，css和js，所以会有各种loader将浏览器没法解析的东西转换成能解析的语言，同时webpack本身无法识别一些文件，也需要Loader做转换，比如css-loader，sass-loader，ts-loader，style-loader，postcss-loader
(1.1) css-loader：因为webpack没办法识别css文件，webpack其实只能理解js和json，所以才会使用需要css-loader去处理css文件引用，将其转为模板字符串
(1.2) style-loader: 将css-loader生成的样式字符串注入到style标签中
(1.3) postcss-loader: 对css做兼容处理，自动增加前缀
执行顺序是postcss-loader->css-loader->style-loader，而配置的时候需要从右向左配置，顺序错误，会导致报错
Loader整体执行阶段类似于洋葱模型，从左到右依次遍历对应的loader，再从右到左执行对应的loader
module.exports = {
module: {
rules: [
{
test: /.css$/,
use: ['style-loader', 'css-loader', 'postcss-loader']
}
]
}
};
vite自身没有loader，可以通过装插件来配置loader，但是没有原生好用，而且vite很多loader功能都原生内嵌了，而且因为工具特性，vite依赖es模块，而浏览器是完全支持es模块的，无需loader做模块转换，整体上都是依靠plugin进行处理
本文从全局视角解析 Vue3 的核心架构，建立源码阅读的整体认知。
┌─────────────────────────────────────────────────────────────┐
│ Vue Application │
└─────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────┐
│ Compiler (编译时) │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ Parse │─►│ Transform │─►│ Codegen │ │
│ │ (解析) │ │ (转换) │ │ (代码生成) │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ │
└─────────────────────────────────────────────────────────────┘
│
▼ render function
┌─────────────────────────────────────────────────────────────┐
│ Runtime (运行时) │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ Reactivity │ │ Renderer │ │ Scheduler │ │
│ │ (响应式) │ │ (渲染器) │ │ (调度器) │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ │
└─────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────┐
│ DOM / Platform │
└─────────────────────────────────────────────────────────────┘
// 模板
<template>
<div>{{ msg }}</div>
</template>
// 编译后的 render 函数
function render(_ctx) {
return _createElementVNode("div", null, _toDisplayString(_ctx.msg))
}
// 运行时执行 render 函数
const vnode = render(ctx)
// patch 到 DOM
patch(null, vnode, container)
// reactive - 对象响应式
const state = reactive({ count: 0 })
// ref - 基本类型响应式
const count = ref(0)
// computed - 计算属性
const double = computed(() => count.value * 2)
// effect - 副作用
effect(() => {
console.log(count.value)
})
┌─────────────────────────────────────────────────────────────┐
│ 响应式流程 │
├─────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────┐ get ┌─────────┐ │
│ │ Proxy │ ─────────► │ track │ ──► 收集当前 effect │
│ └─────────┘ └─────────┘ │
│ │ │
│ │ set │
│ ▼ │
│ ┌─────────┐ ┌─────────┐ │
│ │ trigger │ ─────────► │ effects │ ──► 执行所有 effect │
│ └─────────┘ └─────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
// Dep - 依赖容器
class Dep {
subs: Set<Subscriber> // 订阅者集合
track() {
if (activeSub) {
this.subs.add(activeSub)
}
}
trigger() {
this.subs.forEach(sub => sub.notify())
}
}
// ReactiveEffect - 副作用
class ReactiveEffect {
deps: Link[] // 依赖链表
run() {
activeSub = this
return this.fn()
}
notify() {
this.scheduler ? this.scheduler() : this.run()
}
}
interface VNode {
type: string | Component // 节点类型
props: object | null // 属性
children: VNode[] | string // 子节点
el: Element | null // 真实 DOM
key: string | number // diff key
shapeFlag: number // 节点类型标记
patchFlag: number // 优化标记
}
enum ShapeFlags {
ELEMENT = 1, // 普通元素
FUNCTIONAL_COMPONENT = 1 << 1, // 函数组件
STATEFUL_COMPONENT = 1 << 2, // 有状态组件
TEXT_CHILDREN = 1 << 3, // 文本子节点
ARRAY_CHILDREN = 1 << 4, // 数组子节点
SLOTS_CHILDREN = 1 << 5, // 插槽子节点
TELEPORT = 1 << 6, // Teleport
SUSPENSE = 1 << 7, // Suspense
COMPONENT = STATEFUL_COMPONENT | FUNCTIONAL_COMPONENT
}
const patch = (n1, n2, container) => {
if (n1 === n2) return
// 类型不同，卸载旧节点
if (n1 && !isSameVNodeType(n1, n2)) {
unmount(n1)
n1 = null
}
const { type, shapeFlag } = n2
switch (type) {
case Text:
processText(n1, n2, container)
break
case Fragment:
processFragment(n1, n2, container)
break
default:
if (shapeFlag & ShapeFlags.ELEMENT) {
processElement(n1, n2, container)
} else if (shapeFlag & ShapeFlags.COMPONENT) {
processComponent(n1, n2, container)
}
}
}
const mountComponent = (vnode, container) => {
// 1. 创建组件实例
const instance = createComponentInstance(vnode)
// 2. 设置组件（执行 setup）
setupComponent(instance)
// 3. 设置渲染副作用
setupRenderEffect(instance, vnode, container)
}
const setupRenderEffect = (instance, vnode, container) => {
const effect = new ReactiveEffect(() => {
if (!instance.isMounted) {
// 首次挂载
const subTree = instance.render()
patch(null, subTree, container)
instance.subTree = subTree
instance.isMounted = true
} else {
// 更新
const nextTree = instance.render()
patch(instance.subTree, nextTree, container)
instance.subTree = nextTree
}
})
effect.run()
}
const queue: SchedulerJob[] = []
let isFlushing = false
function queueJob(job) {
if (!queue.includes(job)) {
queue.push(job)
queueFlush()
}
}
function queueFlush() {
if (!isFlushing) {
isFlushing = true
Promise.resolve().then(flushJobs)
}
}
function flushJobs() {
queue.sort((a, b) => getId(a) - getId(b))
for (const job of queue) {
job()
}
queue.length = 0
isFlushing = false
}
const resolvedPromise = Promise.resolve()
function nextTick(fn?) {
return fn
? resolvedPromise.then(fn)
: resolvedPromise
}
interface ComponentInternalInstance {
uid: number // 唯一 ID
type: Component // 组件定义
parent: ComponentInternalInstance | null
// 状态
data: object // data()
props: object // props
setupState: object // setup() 返回值
ctx: object // 渲染上下文
// 渲染
render: Function // render 函数
subTree: VNode // 渲染的 VNode 树
effect: ReactiveEffect // 渲染副作用
// 生命周期
isMounted: boolean
isUnmounted: boolean
// 生命周期钩子
bc: Function[] | null // beforeCreate
c: Function[] | null // created
bm: Function[] | null // beforeMount
m: Function[] | null // mounted
bu: Function[] | null // beforeUpdate
u: Function[] | null // updated
bum: Function[] | null // beforeUnmount
um: Function[] | null // unmounted
}
function setupComponent(instance) {
const { props, children } = instance.vnode
// 初始化 props
initProps(instance, props)
// 初始化 slots
initSlots(instance, children)
// 执行 setup
const { setup } = instance.type
if (setup) {
const setupResult = setup(instance.props, {
attrs: instance.attrs,
slots: instance.slots,
emit: instance.emit,
expose: instance.expose
})
handleSetupResult(instance, setupResult)
}
}
enum PatchFlags {
TEXT = 1, // 动态文本
CLASS = 1 << 1, // 动态 class
STYLE = 1 << 2, // 动态 style
PROPS = 1 << 3, // 动态 props
FULL_PROPS = 1 << 4, // 有动态 key
NEED_HYDRATION = 1 << 5,
STABLE_FRAGMENT = 1 << 6,
KEYED_FRAGMENT = 1 << 7,
UNKEYED_FRAGMENT = 1 << 8,
NEED_PATCH = 1 << 9,
DYNAMIC_SLOTS = 1 << 10,
HOISTED = -1, // 静态提升
BAIL = -2 // 退出优化
}
// 编译优化：只追踪动态节点
const _hoisted_1 = createVNode("div", null, "static")
function render() {
return (openBlock(), createBlock("div", null, [
_hoisted_1, // 静态提升
createVNode("span", null, ctx.msg, PatchFlags.TEXT) // 动态节点
]))
}
┌─────────────────────────────────────────────────────────────┐
│ Vue 渲染流程 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. createApp(App).mount('#app') │
│ │ │
│ ▼ │
│ 2. 创建 VNode │
│ │ │
│ ▼ │
│ 3. render(vnode, container) │
│ │ │
│ ▼ │
│ 4. patch(null, vnode, container) │
│ │ │
│ ▼ │
│ 5. processComponent → mountComponent │
│ │ │
│ ├── createComponentInstance │
│ ├── setupComponent (执行 setup) │
│ └── setupRenderEffect │
│ │ │
│ ▼ │
│ 6. ReactiveEffect.run() │
│ │ │
│ ▼ │
│ 7. instance.render() → subTree VNode │
│ │ │
│ ▼ │
│ 8. patch(null, subTree, container) │
│ │ │
│ ▼ │
│ 9. 递归处理子节点 → 挂载到 DOM │
│ │
└─────────────────────────────────────────────────────────────┘
Vue3 架构的核心：
📦 源码地址：github.com/vuejs/core
下一篇：响应式系统详解
如果觉得有帮助，欢迎点赞收藏 👍
AJAX 是 Asynchronous JavaScript and XML 的缩写，翻译为 “异步的 JavaScript 和 XML”。
补充：虽然名字里有 XML，但现在实际开发中几乎都用JSON（更轻量、易解析）来传输数据，AJAX 只是沿用了历史名称。
AJAX 的核心是浏览器提供的 XMLHttpRequest 对象（简称 XHR），现代浏览器也提供了更易用的 fetch API。其基本工作流程如下：
// 1. 创建XHR对象
const xhr = new XMLHttpRequest();
// 2. 配置请求：请求方式(GET)、URL、是否异步(true)
xhr.open('GET', 'https://jsonplaceholder.typicode.com/todos/1', true);
// 3. 监听请求状态变化（核心）
xhr.onreadystatechange = function() {
// readyState=4 表示请求完成；status=200 表示响应成功
if (xhr.readyState === 4 && xhr.status === 200) {
// 4. 解析服务器返回的JSON数据
const data = JSON.parse(xhr.responseText);
// 5. 局部更新页面（比如把数据显示到id为result的元素里）
document.getElementById('result').innerHTML = `
<h3>任务标题：${data.title}</h3>
<p>是否完成：${data.completed ? '是' : '否'}</p>
`;
}
};
// 处理请求失败的情况
xhr.onerror = function() {
document.getElementById('result').innerHTML = '请求失败！';
};
// 4. 发送请求
xhr.send();
fetch 是 AJAX 的现代替代方案，基于 Promise，语法更优雅：
// 1. 发送GET请求
fetch('https://jsonplaceholder.typicode.com/todos/1')
// 2. 处理响应：先判断是否成功，再解析为JSON
.then(response => {
if (!response.ok) {
throw new Error('请求失败，状态码：' + response.status);
}
return response.json();
})
// 3. 使用数据更新页面
.then(data => {
document.getElementById('result').innerHTML = `
<h3>任务标题：${data.title}</h3>
<p>是否完成：${data.completed ? '是' : '否'}</p>
`;
})
// 4. 捕获异常
.catch(error => {
document.getElementById('result').innerHTML = error.message;
});
http://localhost:8080不能请求http://baidu.com），跨域需要服务器配置 CORS 或使用代理。onreadystatechange）或 Promise 的then里处理返回数据。XMLHttpRequest对象（或现代的fetch）。fetch（结合 Promise/async-await）已逐步替代传统 XHR，是 AJAX 的主流实现方式。