给你一个 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
}
}
复杂度分析
给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。
给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。
会议将会按以下方式分配给会议室：
返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。
半闭区间 [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 <= 1001 <= meetings.length <= 105meetings[i].length == 20 <= starti < endi <= 5 * 105starti 的所有值 互不相同
由于 $n\le 100$，可以直接按照题目模拟：
按开始时间排序，依次安排 meetings
维护每个会议室的 最早可用时间 $t$。每次安排会议$[start, end)$时，将那些 $t$ 早于 $start$ 的会议室的 $t$ 设为 $start$。这样处理后只需从中选择 $t$ 最早的会议室即可（如果有相等的选下标最小的）。
同时维护 $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))
按照时间顺序模拟开会过程。
对于会议 $[\textit{start},\textit{end})$，我们需要知道：
这两类会议室是互补关系，伴随着会议的开始和结束，会议室在这两类中来回倒：
在上述模拟的过程中，每使用一个编号为 $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 }
欢迎关注 B站@灵茶山艾府
因为“当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议”，因此有重要性质：会议开始的相对顺序不会改变。我们只需要按顺序模拟每个会议分配给哪个会议室即可。
复杂度 $\mathcal{O}(m\log m + nm)$，其中 $m$ 是会议的数量。具体实现见参考代码，注意会议的结束时间可能超出 int 的范围。
###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++
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;
}
};
给你一个顾客访问商店的日志，用一个下标从 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 <= 105customers 只包含字符 'Y' 和 'N' 。利用前缀和，后缀和统计N，Y的数字即可，最后计算出最小的答案。
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;
}
}
如果有问题,欢迎评论区交流, 如果有帮助到你，请给题解点个赞和收藏哈~~~
把 $\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
}
欢迎关注 B站@灵茶山艾府
为了方便计算前（后）缀和，我们认为 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++
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;
}
};
为了使得幸福值之和尽可能大，我们应该优先选择幸福值大的孩子。因此，我们可以对孩子按照幸福值从大到小排序，然后依次选择 $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}$ 的长度。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
给你一个长度为 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 * 1051 <= happiness[i] <= 1081 <= k <= n为了使选择的 $k$ 个孩子的幸福值之和最大，应遵循如下贪心策略：按照幸福值递减的顺序选择幸福值最大的 $k$ 个孩子。理由如下。
如果将幸福值最大的 $k$ 个孩子中的任意一个孩子更换成一个幸福值较小的孩子，则更换之后的孩子的幸福值一定不变或减少，不可能增加，因此幸福值之和不可能更大。
当选择幸福值最大的 $k$ 个孩子时，如果这 $k$ 个孩子的初始幸福值都不小于 $k - 1$ 则幸福值之和的总减少量等于 $\dfrac{k(k + 1)}{2}$，如果这 $k$ 个孩子中存在孩子的初始幸福值小于 $k - 1$ 则幸福值之和的总减少量小于 $\dfrac{k(k + 1)}{2}$。假设两个孩子的幸福值分别为 $x$ 和 $y$，其中 $x > y$，则先选择 $x$ 后选择 $y$ 的幸福值之和等于 $x + \max(y - 1, 0)$，先选择 $y$ 后选择 $x$ 的幸福值之和等于 $y + \max(x - 1, 0)$，由于 $x > y > 0$，因此 $\max(x - 1, 0) = x - 1$，$x + \max(y - 1, 0) \ge y + \max(x - 1, 0)$，即先选择 $x$ 后选择 $y$ 的方案更优。
根据贪心策略，计算选中的孩子的幸福值之和的最大值的方法如下。
将数组 $\textit{happiness}$ 按升序排序。
用 $n$ 表示数组 $\textit{happiness}$ 的长度，反向遍历排序后的数组 $\textit{happiness}$，对于每个 $1 \le i \le k$，需要选择幸福值为 $\textit{happiness}[n - i]$ 的孩子，该孩子被选择时的幸福值为 $\max(\textit{happiness}[n - i] - (i - 1), 0)$，计算选中的孩子的幸福值之和。
实现方面，反向遍历排序后的数组 $\textit{happiness}$ 时，当遇到 $\textit{happiness}[n - i] \le i - 1$ 时，其余孩子的幸福值一定都是 $0$，此时即可结束遍历。
遍历结束之后，即可得到选中的孩子的幸福值之和的最大值。
###Java
class Solution {
public long maximumHappinessSum(int[] happiness, int k) {
long sum = 0;
Arrays.sort(happiness);
int n = happiness.length;
for (int i = 1; i <= k && happiness[n - i] > i - 1; i++) {
int curr = happiness[n - i] - (i - 1);
sum += curr;
}
return sum;
}
}
###C#
public class Solution {
public long MaximumHappinessSum(int[] happiness, int k) {
long sum = 0;
Array.Sort(happiness);
int n = happiness.Length;
for (int i = 1; i <= k && happiness[n - i] > i - 1; i++) {
int curr = happiness[n - i] - (i - 1);
sum += curr;
}
return sum;
}
}
时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{happiness}$ 的长度。将数组 $\textit{happiness}$ 排序的时间是 $O(n \log n)$，排序后遍历数组 $\textit{happiness}$ 计算选中的孩子的幸福值之和的最大值的时间是 $O(n)$，因此时间复杂度是 $O(n \log n)$。
空间复杂度：$O(\log n)$，其中 $n$ 是数组 $\textit{happiness}$ 的长度。排序的递归调用栈空间是 $O(\log n)$。
本质是选一些数求和，为了让和最大，我们要选 $\textit{happiness}$ 最大的 $k$ 个数。
这 $k$ 个数要按照什么顺序选呢？
由于小的数减成 $0$ 就不再减少了，优先选大的数更好。
比如 $2,1,1$，如果按照 $1,1,2$ 的顺序选，答案为 $1+0+0=1$；但按照 $2,1,1$ 的顺序选，答案为 $2+0+0=2$，更优。
###py
class Solution:
def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
happiness.sort(reverse=True)
ans = 0
for i, x in enumerate(happiness[:k]):
if x <= i:
break
ans += x - i
return ans
###java
class Solution {
public long maximumHappinessSum(int[] happiness, int k) {
Arrays.sort(happiness);
int n = happiness.length;
long ans = 0;
for (int i = n - 1; i >= n - k && happiness[i] > n - 1 - i; i--) {
ans += happiness[i] - (n - 1 - i);
}
return ans;
}
}
###cpp
class Solution {
public:
long long maximumHappinessSum(vector<int>& happiness, int k) {
ranges::sort(happiness, greater());
long long ans = 0;
for (int i = 0; i < k && happiness[i] > i; i++) {
ans += happiness[i] - i;
}
return ans;
}
};
###c
int cmp(const void* a, const void* b) {
return *(int*)b - *(int*)a;
}
long long maximumHappinessSum(int* happiness, int happinessSize, int k) {
qsort(happiness, happinessSize, sizeof(int), cmp);
long long ans = 0;
for (int i = 0; i < k && happiness[i] > i; i++) {
ans += happiness[i] - i;
}
return ans;
}
###go
func maximumHappinessSum(happiness []int, k int) (ans int64) {
slices.SortFunc(happiness, func(a, b int) int { return b - a })
for i, x := range happiness[:k] {
if x <= i {
break
}
ans += int64(x - i)
}
return
}
###js
var maximumHappinessSum = function(happiness, k) {
happiness.sort((a, b) => b - a);
let ans = 0;
for (let i = 0; i < k && happiness[i] > i; i++) {
ans += happiness[i] - i;
}
return ans;
};
###rust
impl Solution {
pub fn maximum_happiness_sum(mut happiness: Vec<i32>, k: i32) -> i64 {
happiness.sort_unstable_by_key(|x| -x);
let mut ans = 0;
for (i, &x) in happiness[..k as usize].iter().enumerate() {
if x <= i as i32 {
break;
}
ans += (x - i as i32) as i64;
}
ans
}
}
欢迎关注 B站@灵茶山艾府
每次应该选择当前幸福值最高的孩子。由于每个孩子在没被选中时，幸福值都会下降相同的量，所以幸福值的相对大小关系不会改变。
因此将孩子按幸福值从大到小排序，依次选择孩子即可。复杂度 $\mathcal{O}(n\log n)$。
###c++
class Solution {
public:
long long maximumHappinessSum(vector<int>& happiness, int K) {
int n = happiness.size();
// 将孩子按幸福值排序
sort(happiness.begin(), happiness.end());
long long ans = 0;
// 按幸福值从大到小选择孩子
for (int i = n - 1; i >= n - K; i--) ans += max(0, happiness[i] - (n - 1 - i));
return ans;
}
};
为了使得需要的箱子数量尽可能少，我们应该优先使用容量大的箱子。因此，我们可以对箱子按照容量从大到小排序，然后依次使用箱子，直到所有的苹果都被分装完，返回此时使用的箱子数量。
###python
class Solution:
def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
capacity.sort(reverse=True)
s = sum(apple)
for i, c in enumerate(capacity, 1):
s -= c
if s <= 0:
return i
###java
class Solution {
public int minimumBoxes(int[] apple, int[] capacity) {
Arrays.sort(capacity);
int s = 0;
for (int x : apple) {
s += x;
}
for (int i = 1, n = capacity.length;; ++i) {
s -= capacity[n - i];
if (s <= 0) {
return i;
}
}
}
}
###cpp
class Solution {
public:
int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
sort(capacity.rbegin(), capacity.rend());
int s = accumulate(apple.begin(), apple.end(), 0);
for (int i = 1;; ++i) {
s -= capacity[i - 1];
if (s <= 0) {
return i;
}
}
}
};
###go
func minimumBoxes(apple []int, capacity []int) int {
sort.Ints(capacity)
s := 0
for _, x := range apple {
s += x
}
for i := 1; ; i++ {
s -= capacity[len(capacity)-i]
if s <= 0 {
return i
}
}
}
###ts
function minimumBoxes(apple: number[], capacity: number[]): number {
capacity.sort((a, b) => b - a);
let s = apple.reduce((acc, cur) => acc + cur, 0);
for (let i = 1; ; ++i) {
s -= capacity[i - 1];
if (s <= 0) {
return i;
}
}
}
###rust
impl Solution {
pub fn minimum_boxes(apple: Vec<i32>, mut capacity: Vec<i32>) -> i32 {
capacity.sort();
let mut s: i32 = apple.iter().sum();
let n = capacity.len();
let mut i = 1;
loop {
s -= capacity[n - i];
if s <= 0 {
return i as i32;
}
i += 1;
}
}
}
时间复杂度 $O(m \times \log m + n)$，空间复杂度 $O(\log m)$。其中 $m$ 和 $n$ 分别是数组 $\textit{capacity}$ 和 $\textit{apple}$ 的长度。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
