LeetCode Go · 数组与矩阵（4）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

2482. 行和列中一和零的差值

中等1 种解法

标签：数组、矩阵、模拟

题目、示例与约束

给你一个下标从 0 开始的 m x n 二进制矩阵 grid 。

我们按照如下过程，定义一个下标从 0 开始的 m x n 差值矩阵 diff ：

• 令第 i 行一的数目为 onesRowi 。
• 令第 j 列一的数目为 onesColj 。
• 令第 i 行零的数目为 zerosRowi 。
• 令第 j 列零的数目为 zerosColj 。
• diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj

请你返回差值矩阵 diff 。

 

示例 1：

输入：grid = [[0,1,1],[1,0,1],[0,0,1]]
输出：[[0,0,4],[0,0,4],[-2,-2,2]]
解释：
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[2][0] = onesRow2 + onesCol0 - zerosRow2 - zerosCol0 = 1 + 1 - 2 - 2 = -2
- diff[2][1] = onesRow2 + onesCol1 - zerosRow2 - zerosCol1 = 1 + 1 - 2 - 2 = -2
- diff[2][2] = onesRow2 + onesCol2 - zerosRow2 - zerosCol2 = 1 + 3 - 2 - 0 = 2

示例 2：

输入：grid = [[1,1,1],[1,1,1]]
输出：[[5,5,5],[5,5,5]]
解释：
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• grid[i][j] 要么是 0 ，要么是 1 。

方法一：模拟 · Go 实现

思考

$diff[i][j]=onesRo{w}_i+onesCo{l}_j-zerosRo{w}_i-zerosCo{l}_j$，而零的个数由行宽列高减去一的个数得到。 $mn\le {10}^5$，先统计每行每列的 $1$，再填每个格子。

根据题意模拟即可。

时间复杂度 $O(m\times n)$，忽略答案的空间消耗，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

func onesMinusZeros(grid [][]int) [][]int {
	m, n := len(grid), len(grid[0])
	rows := make([]int, m)
	cols := make([]int, n)
	diff := make([][]int, m)
	for i, row := range grid {
		diff[i] = make([]int, n)
		for j, v := range row {
			rows[i] += v
			cols[j] += v
		}
	}
	for i, r := range rows {
		for j, c := range cols {
			diff[i][j] = r + c - (n - r) - (m - c)
		}
	}
	return diff
}

力扣原题 · Doocs 题解来源

2553. 分割数组中数字的数位

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个正整数数组 nums ，请你返回一个数组 answer ，你需要将 nums 中每个整数进行数位分割后，按照 nums 中出现的 相同顺序 放入答案数组中。

对一个整数进行数位分割，指的是将整数各个数位按原本出现的顺序排列成数组。

• 比方说，整数 10921 ，分割它的各个数位得到 [1,0,9,2,1] 。

 

示例 1：

输入：nums = [13,25,83,77]
输出：[1,3,2,5,8,3,7,7]
解释：
- 分割 13 得到 [1,3] 。
- 分割 25 得到 [2,5] 。
- 分割 83 得到 [8,3] 。
- 分割 77 得到 [7,7] 。
answer = [1,3,2,5,8,3,7,7] 。answer 中的数字分割结果按照原数字在数组中的相同顺序排列。

示例 2：

输入：nums = [7,1,3,9]
输出：[7,1,3,9]
解释：nums 中每个整数的分割是它自己。
answer = [7,1,3,9] 。

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 105

方法一：模拟 · Go 实现

思考

按原顺序把每个整数拆成十进制数位。除十得到的是逆序数位，收集后反转再拼到答案即可。

将数组中的每个数字进行数位分割，然后将分割后的数字依次放入答案数组中。

时间复杂度 $O(n\times {\log }_{10}M)$，空间复杂度 $O(n\times {\log }_{10}M)$，其中 $n$ 为数组 $nums$ 的长度，而 $M$ 为数组 $nums$ 中的最大值。

func separateDigits(nums []int) (ans []int) {
	for _, x := range nums {
		t := []int{}
		for ; x > 0; x /= 10 {
			t = append(t, x%10)
		}
		for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
			t[i], t[j] = t[j], t[i]
		}
		ans = append(ans, t...)
	}
	return
}

力扣原题 · Doocs 题解来源

2639. 查询网格图中每一列的宽度

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大 字符串长度 。

• 比方说，如果 grid = [[-10], [3], [12]] ，那么唯一一列的宽度是 3 ，因为 -10 的字符串长度为 3 。

请你返回一个大小为 n 的整数数组 ans ，其中 ans[i] 是第 i 列的宽度。

一个有 len 个数位的整数 x ，如果是非负数，那么 字符串长度 为 len ，否则为 len + 1 。

 

示例 1：

输入：grid = [[1],[22],[333]]
输出：[3]
解释：第 0 列中，333 字符串长度为 3 。

示例 2：

输入：grid = [[-15,1,3],[15,7,12],[5,6,-2]]
输出：[3,1,2]
解释：
第 0 列中，只有 -15 字符串长度为 3 。
第 1 列中，所有整数的字符串长度都是 1 。
第 2 列中，12 和 -2 的字符串长度都为 2 。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -109 <= grid[r][c] <= 109

方法一：模拟 · Go 实现

思考

列宽是该列数字十进制表示的最大长度，含负号。矩阵不超过 $100\times 100$，按列取 str 长度的最大值即可，无需更复杂结构。

我们记矩阵的列数为 $n$，创建一个长度为 $n$ 的数组 $ans$，其中 $ans[i]$ 表示第 $i$ 列的宽度。初始时 $ans[i]=0$。

遍历矩阵中的每一行，对于每一行中的每个元素，计算其字符串长度 $w$，并更新 $ans[j]$ 的值为 $max(ans[j],w)$。

遍历完所有行后，数组 $ans$ 中的每个元素即为对应列的宽度。

时间复杂度 $O(m\times n)$，空间复杂度 $O(\log M)$。其中 $m$ 和 $n$ 分别为矩阵的行数和列数，而 $M$ 为矩阵中的最大元素绝对值。

func findColumnWidth(grid [][]int) []int {
	ans := make([]int, len(grid[0]))
	for _, row := range grid {
		for j, x := range row {
			w := len(strconv.Itoa(x))
			ans[j] = max(ans[j], w)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2643. 一最多的行

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。

如果有多行包含最多的 1 ，只需要选择 行下标最小 的那一行。

返回一个由行下标和该行中 1 的数量组成的数组。

 

示例 1：

输入：mat = [[0,1],[1,0]]
输出：[0,1]
解释：两行中 1 的数量相同。所以返回下标最小的行，下标为 0 。该行 1 的数量为 1 。所以，答案为 [0,1] 。 

示例 2：

输入：mat = [[0,0,0],[0,1,1]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

示例 3：

输入：mat = [[0,0],[1,1],[0,0]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

 

提示：

• m == mat.length 
• n == mat[i].length 
• 1 <= m, n <= 100 
• mat[i][j] 为 0 或 1

方法一：模拟 · Go 实现

思考

矩阵只含 $0/1$，求 $1$ 最多的行（并列取最小行号）。行列至多 $100$，逐行求和并维护当前最优即可，无需预处理。

我们初始化一个数组 $\mathit{\text{ans}}=[0,0]$，用于记录最多 $1$ 的行的下标和 $1$ 的数量。

然后遍历矩阵的每一行，对于每一行：

• 计算该行 $1$ 的数量 $\mathit{\text{cnt}}$（由于矩阵中只包含 $0$ 和 $1$，我们可以直接对该行求和）；
• 如果 $\mathit{\text{ans}}[1]<\mathit{\text{cnt}}$，则更新 $\mathit{\text{ans}}=[i,\mathit{\text{cnt}}]$。

遍历结束后，返回 $\mathit{\text{ans}}$。

时间复杂度 $O(m\times n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$。

func rowAndMaximumOnes(mat [][]int) []int {
	ans := []int{0, 0}
	for i, row := range mat {
		cnt := 0
		for _, x := range row {
			cnt += x
		}
		if ans[1] < cnt {
			ans = []int{i, cnt}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2644. 找出可整除性得分最大的整数

简单1 种解法

标签：数组

题目、示例与约束

给你两个整数数组 nums 和 divisors 。

divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。

返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。

 

示例 1：

输入：nums = [2,9,15,50], divisors = [5,3,7,2]

输出：2

解释：

divisors[0] 的可整除性分数为 2 因为 nums[2] 和 nums[3] 能被 5 整除。

divisors[1] 的可整除性分数为 2 因为 nums[1] 和 nums[2] 能被 3 整除。

divisors[2] 的可整除性分数为 0 因为 nums 中没有数字能被 7 整除。

divisors[3] 的可整除性分数为 2 因为 nums[0] 和 nums[3] 能够被 2 整除。

因为 divisors[0] 、divisor[1] 和 divisors[3] 有相同的可整除性分数，我们返回更小的那个 divisors[3]。

示例 2：

输入：nums = [4,7,9,3,9], divisors = [5,2,3]

输出：3

解释：

divisors[0] 的可整除性分数为 0 因为 nums 中没有数字能被 5 整除。

divisors[1] 的可整除性分数为 1 因为只有 nums[0] 能被 2 整除。

divisors[2] 的可整除性分数为 3 因为 nums[2] ，nums[3] 和 nums[4] 能被 3 整除。

示例 3：

输入：nums = [20,14,21,10], divisors = [10,16,20]

输出：10

解释：

divisors[0] 的可整除性分数为 2 因为 nums[0] 和 nums[3] 能被 10 整除。

divisors[1] 的可整除性分数为 0 因为 nums 中没有数字能被 16 整除。

divisors[2] 的可整除性分数为 1 因为 nums[0] 能被 20 整除。

因为 divisors[0] 的可整除性分数最大，我们返回 divisors[0]。

 

提示：

• 1 <= nums.length, divisors.length <= 1000
• 1 <= nums[i], divisors[i] <= 109

方法一：枚举 · Go 实现

思考

得分是 $nums$ 中能被该除数整除的个数，并列取最小除数。两数组长度 $\le 1000$，枚举每个除数扫描 $nums$ 即可。

维护当前最大计数及对应除数，计数相等时改取更小的 $div$。

我们可以枚举 $divisors$ 中的每个元素 $div$，计算 $nums$ 中有多少个元素能被 $div$ 整除，记为 $cnt$。

• 如果 $cnt$ 大于当前最大的可整除性得分 $mx$，则更新 $mx=cnt$，并且更新 $ans=div$。
• 如果 $cnt$ 等于 $mx$ 并且 $div$ 小于 $ans$，则更新 $ans=div$。

最后返回 $ans$ 即可。

时间复杂度 $O(m\times n)$，其中 $m$ 和 $n$ 分别是 $nums$ 和 $divisors$ 的长度。空间复杂度 $O(1)$。

func maxDivScore(nums []int, divisors []int) int {
	ans, mx := divisors[0], 0
	for _, div := range divisors {
		cnt := 0
		for _, x := range nums {
			if x%div == 0 {
				cnt++
			}
		}
		if mx < cnt {
			ans, mx = div, cnt
		} else if mx == cnt && ans > div {
			ans = div
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2660. 保龄球游戏的获胜者

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你两个下标从 0 开始的整数数组 player1 和 player2 ，分别表示玩家 1 和玩家 2 击中的瓶数。

保龄球比赛由 n 轮组成，每轮的瓶数恰好为 10 。

假设玩家在第 i 轮中击中 xi 个瓶子。玩家第 i 轮的价值为：

• 如果玩家在该轮的前两轮的任何一轮中击中了 10 个瓶子，则为 2xi 。
• 否则，为 xi 。

玩家的得分是其 n 轮价值的总和。

返回

• 如果玩家 1 的得分高于玩家 2 的得分，则为 1 ；
• 如果玩家 2 的得分高于玩家 1 的得分，则为 2 ；
• 如果平局，则为 0 。

 

示例 1：

输入：player1 = [5,10,3,2], player2 = [6,5,7,3]

输出：1

解释：

玩家 1 的分数为 5 + 10 + 2*3 + 2*2 = 25。

玩家 2 的分数为 6 + 5 + 7 + 3 = 21。

示例 2：

输入：player1 = [3,5,7,6], player2 = [8,10,10,2]

输出：2

解释：

玩家 1 的分数为 3 + 5 + 7 + 6 = 21。

玩家 2 的分数为 8 + 10 + 2*10 + 2*2 = 42。

示例 3：

输入：player1 = [2,3], player2 = [4,1]

输出：0

解释：

玩家 1 的分数为 2 + 3 = 5。

玩家 2 的分数为 4 + 1 = 5。

示例 4：

输入：player1 = [1,1,1,10,10,10,10], player2 = [10,10,10,10,1,1,1]

输出：2

解释：

玩家 1 的分数为 1 + 1 + 1 + 10 + 2*10 + 2*10 + 2*10 = 73。

玩家 2 的分数为 is 10 + 2*10 + 2*10 + 2*10 + 2*1 + 2*1 + 1 = 75。

 

提示：

• n == player1.length == player2.length
• 1 <= n <= 1000
• 0 <= player1[i], player2[i] <= 10

方法一：模拟 · Go 实现

思考

得分规则只看前两轮是否击倒 $10$ 瓶。两数组长度 $\le 1000$，按规则累加后比较大小即可，无需更复杂状态。

我们可以用一个函数 $f(arr)$ 计算出两个玩家的得分，分别记为 $a$ 和 $b$，然后根据 $a$ 和 $b$ 的大小关系返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func isWinner(player1 []int, player2 []int) int {
	f := func(arr []int) int {
		s := 0
		for i, x := range arr {
			k := 1
			if (i > 0 && arr[i-1] == 10) || (i > 1 && arr[i-2] == 10) {
				k = 2
			}
			s += k * x
		}
		return s
	}
	a, b := f(player1), f(player2)
	if a > b {
		return 1
	}
	if b > a {
		return 2
	}
	return 0
}

力扣原题 · Doocs 题解来源

2672. 有相同颜色的相邻元素数目

中等1 种解法

标签：数组

题目、示例与约束

给定一个整数 n 表示一个长度为 n 的数组  colors，初始所有元素均为 0 ，表示是 未染色 的。同时给定一个二维整数数组 queries，其中 queries[i] = [indexi, colori]。对于第 i 个 查询：

• 将 colors[indexi] 染色为 colori。
• 统计 colors 中颜色相同的相邻对的数量（无论 colori）。

请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作的答案。

 

示例 1：

输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

输出：[0,1,1,0,2]

解释：

• 一开始 colors = [0,0,0,0]，其中 0 表示数组中未染色的元素。
• 在第 1 次查询后 colors = [2,0,0,0]。颜色相同的相邻对的数量是 0。
• 在第 2 次查询后 colors = [2,2,0,0]。颜色相同的相邻对的数量是 1。
• 在第 3 次查询后 colors = [2,2,0,1]。颜色相同的相邻对的数量是 1。
• 在第 4 次查询后 colors = [2,1,0,1]。颜色相同的相邻对的数量是 0。
• 在第 5 次查询后 colors = [2,1,1,1]。颜色相同的相邻对的数量是 2。

示例 2：

输入：n = 1, queries = [[0,100000]]

输出：[0]

解释：

在第一次查询后 colors = [100000]。颜色相同的相邻对的数量是 0。

 

提示：

• 1 <= n <= 105
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= indexi <= n - 1
• 1 <=  colori <= 105

方法一 · Go 实现

思考

每次只改一个位置的颜色，要报告当前相邻同色对数。若每次重扫整列， $n,q\le {10}^5$ 平方。一对相邻关系只受该点及其左右影响。

改色前先撤掉与左右已形成的同色对，写入新色后再按新值补上。未着色（ $0$）不计入。维护全局计数 $x$。

func colorTheArray(n int, queries [][]int) (ans []int) {
	nums := make([]int, n)
	x := 0
	for _, q := range queries {
		i, c := q[0], q[1]
		if i > 0 && nums[i] > 0 && nums[i-1] == nums[i] {
			x--
		}
		if i < n-1 && nums[i] > 0 && nums[i+1] == nums[i] {
			x--
		}
		if i > 0 && nums[i-1] == c {
			x++
		}
		if i < n-1 && nums[i+1] == c {
			x++
		}
		ans = append(ans, x)
		nums[i] = c
	}
	return
}

力扣原题 · Doocs 题解来源

2717. 半有序排列

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个下标从 0 开始、长度为 n 的整数排列 nums 。

如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：

• 选择 nums 中相邻的两个元素，然后交换它们。

返回使 nums 变成 半有序排列 所需的最小操作次数。

排列 是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。

 

示例 1：

输入：nums = [2,1,4,3]
输出：2
解释：可以依次执行下述操作得到半有序排列：
1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明，要让 nums 成为半有序排列，不存在执行操作少于 2 次的方案。

示例 2：

输入：nums = [2,4,1,3]
输出：3
解释：
可以依次执行下述操作得到半有序排列：
1 - 交换下标 1 和下标 2 对应元素。排列变为 [2,1,4,3] 。
2 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
3 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明，要让 nums 成为半有序排列，不存在执行操作少于 3 次的方案。

示例 3：

输入：nums = [1,3,4,2,5]
输出：0
解释：这个排列已经是一个半有序排列，无需执行任何操作。

 

提示：

• 2 <= nums.length == n <= 50
• 1 <= nums[i] <= 50
• nums 是一个 排列

方法一：寻找 1 和 n 的位置 · Go 实现

思考

相邻交换把 $1$ 换到最左、 $n$ 换到最右，求最少次数。任意排列可用相邻交换排序，但我们只关心这两个键的位移。

$1$ 左移 $i$ 步， $n$ 右移 $n-1-j$ 步。若 $1$ 最初在 $n$ 右侧，两者相向经过时少算一次交换，故再减 $1$。一次遍历记下两个下标即可。

我们可以先找到 $1$ 和 $n$ 的下标 $i$ 和 $j$，然后根据 $i$ 和 $j$ 的相对位置，判断需要交换的次数。

如果 $i<j$，那么需要交换的次数为 $i+n-j-1$；如果 $i>j$，那么需要交换的次数为 $i+n-j-2$。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

func semiOrderedPermutation(nums []int) int {
	n := len(nums)
	var i, j int
	for k, x := range nums {
		if x == 1 {
			i = k
		}
		if x == n {
			j = k
		}
	}
	k := 1
	if i > j {
		k = 2
	}
	return i + n - j - k
}

力扣原题 · Doocs 题解来源

2728. 计算一个环形街道上的房屋数量 🔒

简单1 种解法

标签：数组、交互

题目、示例与约束

给定一个代表环形街道的类 Street 和一个正整数 k，表示街道上房屋的最大数量（也就是说房屋数量不超过 k ）。每个房屋的门初始时可以是开着的也可以是关着的。

刚开始，你站在一座房子的门前。你的任务是计算街道上的房屋数量。

Street 类包含以下函数：

• void openDoor() ：打开当前房屋的门。
• void closeDoor() ：关闭当前房屋的门。
• boolean isDoorOpen() ：如果当前房屋的门是开着的返回 true ，否则返回 false 。
• void moveRight() ：向右移动到下一座房屋。
• void moveLeft() ：向左移动到上一座房屋。

返回 ans，它表示街道上的房屋数量。

 

示例 1：

输入：street = [0,0,0,0], k = 10
输出：4
解释：街道上有 4 座房屋，它们的门都是关着的。
房屋数量小于 k，即 10。

示例 2：

输入：street = [1,0,1,1,0], k = 5
输出：5
解释：街道上有 5 座房屋，向右移动时第 1、3 和 4 座房屋的门是开着的，其余的门都是关着的。房屋数量等于 k，即 5。

 

解释：

• n  是房屋数量
• 1 <= n <= k <= 103

方法一：遍历 · Go 实现

思考

环形街道上房屋数不超过 $k$，只能通过开关门与左右移动感知。若先关门再转一圈计数，起点门的开闭状态与「是否走完一圈」无法区分。

先向左走 $k$ 步并打开沿途的门，保证整圈门全开。再继续左移：每遇到开着的门就关上并计数，直到再次碰到已关的门，计数即为房屋数。

我们先循环 $k$ 次，每次打开当前房子的门，然后向左移动一格，循环结束后，所有房子的门都是打开的。

然后，我们再循环左移，如果当前房子的门是打开的，就关闭它，房子数加一，继续左移，直到当前房子的门是关闭的，循环结束，返回房子数。

时间复杂度 $O(k)$，其中 $k$ 为题目给定的整数。空间复杂度 $O(1)$。

相似题目：

• 2753. 计算一个环形街道上的房屋数量 🔒 II

/**
 * Definition for a street.
 * type Street interface {
 *     OpenDoor()
 *     CloseDoor()
 *     IsDoorOpen() bool
 *     MoveRight()
 *     MoveLeft()
 * }
 */
func houseCount(street Street, k int) (ans int) {
	for ; k > 0; k-- {
		street.OpenDoor()
		street.MoveLeft()
	}
	for ; street.IsDoorOpen(); street.MoveLeft() {
		ans++
		street.CloseDoor()
	}
	return
}

力扣原题 · Doocs 题解来源

2735. 收集巧克力

中等1 种解法

标签：数组、枚举

题目、示例与约束

给你一个长度为 n、下标从 0 开始的整数数组 nums，nums[i] 表示收集位于下标 i 处的巧克力成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。

在一步操作中，你可以用成本 x 执行下述行为：

• 同时修改所有巧克力的类型，将巧克力的类型 ith 修改为类型 ((i + 1) mod n)th。

假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。

 

示例 1：

输入：nums = [20,1,15], x = 5
输出：13
解释：最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。
接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。
然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。
因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。

示例 2：

输入：nums = [1,2,3], x = 4
输出：6
解释：我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 1 <= x <= 109

方法一：枚举 · Go 实现

思考

买第 $i$ 种巧克力的花费是环形左移若干次后该位置见过的最小值，每次左移另付 $x$。枚举每种糖的购买时机互相耦合，直接搜索不可行。

全局左移次数 $j$ 对所有种类相同，且 $j\ge n$ 不会再降低购买价。预处理 $f[i][j]$ 为第 $i$ 种糖在至多 $j$ 次左移下的最低价，再枚举 $j$ 取 $\sum _{i}f[i][j]+x\cdot j$ 的最小。

我们考虑枚举操作的次数，定义 $f[i][j]$ 表示第 $i$ 个巧克力进行了 $j$ 次操作后的最小成本。

对于第 $i$ 个巧克力：

• 如果 $j=0$，即没有进行操作，那么 $f[i][j]=nums[i]$；
• 如果 $0<j\le n-1$，那么它的最小成本就是下标范围为 $[i,..(i-j+n)modn]$ 的最小成本，即 $f[i][j]=min\{nums[i],nums[i-1],\cdots ,nums[(i-j+n)modn]\}$，或者可以写成 $f[i][j]=min\{f[i][j-1],nums[(i-j+n)modn]\}$。
• 如果 $j\ge n$，由于当 $j=n-1$ 时，已经覆盖了所有最小成本，如果 $j$ 继续增大，那么最小成本不会再变化，但是操作次数的增加却会导致最终的成本增加，因此，我们不需要考虑 $j\ge n$ 的情况。

综上，我们可以得到状态转移方程：

$$f[i][j]=\{\begin{array}{ll}nums[i],& j=0\\ min(f[i][j-1],nums[(i-j+n)modn]),& 0<j\le n-1\end{array}$$

最后，我们只需要枚举操作的次数 $j$，计算出每种操作次数下的最小成本，取最小值即可。即答案为 $\underset{0\le j\le n-1}{min}\sum _{i=0}^{n-1}f[i][j]+x\times j$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 为数组 $nums$ 的长度。

func minCost(nums []int, x int) int64 {
	n := len(nums)
	f := make([][]int, n)
	for i, v := range nums {
		f[i] = make([]int, n)
		f[i][0] = v
		for j := 1; j < n; j++ {
			f[i][j] = min(f[i][j-1], nums[(i-j+n)%n])
		}
	}
	ans := 1 << 60
	for j := 0; j < n; j++ {
		cost := x * j
		for i := 0; i < n; i++ {
			cost += f[i][j]
		}
		ans = min(ans, cost)
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2765. 最长交替子数组

简单1 种解法

标签：数组、枚举

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个 交替子数组 ：

• m 大于 1 。
• s1 = s0 + 1 。
• 下标从 0 开始的子数组 s 与数组 [s0, s1, s0, s1,...,s(m-1) % 2] 一样。也就是说，s1 - s0 = 1 ，s2 - s1 = -1 ，s3 - s2 = 1 ，s4 - s3 = -1 ，以此类推，直到 s[m - 1] - s[m - 2] = (-1)m 。

请你返回 nums 中所有 交替 子数组中，最长的长度，如果不存在交替子数组，请你返回 -1 。

子数组是一个数组中一段连续 非空 的元素序列。

 

示例 1：

输入：nums = [2,3,4,3,4]

输出：4

解释：交替子数组有 [2,3]，[3,4]，[3,4,3] 和 [3,4,3,4]。最长的子数组为 [3,4,3,4]，长度为 4。

 

示例 2：

输入：nums = [4,5,6]

输出：2

解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2 。

 

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 104

方法一：枚举 · Go 实现

思考

交替子数组从差为 $1$ 起手，之后相邻差在 $1$ 与 $-1$ 之间翻转，求最长长度（至少为 $2$）。 $n\le 100$，枚举左端再延伸即可。

对每个起点 $i$ 用期望差 $k=1$ 向右走，匹配则翻转 $k$。长度大于 $1$ 时更新答案，否则保持 $-1$。

我们可以枚举子数组的左端点 $i$，对于每个 $i$，我们需要找到最长的满足条件的子数组。我们可以从 $i$ 开始向右遍历，每次遇到相邻元素差值不满足交替条件时，我们就找到了一个满足条件的子数组。我们可以用一个变量 $k$ 来记录当前元素的差值应该是 $1$ 还是 $-1$，如果当前元素的差值应该是 $-k$，那么我们就将 $k$ 取反。当我们找到一个满足条件的子数组 $nums[i..j]$ 时，我们更新答案为 $max(ans,j-i+1)$。

时间复杂度 $O(n^2)$，其中 $n$ 是数组的长度。我们需要枚举子数组的左端点 $i$，对于每个 $i$，我们需要 $O(n)$ 的时间来找到最长的满足条件的子数组。空间复杂度 $O(1)$。

func alternatingSubarray(nums []int) int {
	ans, n := -1, len(nums)
	for i := range nums {
		k := 1
		j := i
		for ; j+1 < n && nums[j+1]-nums[j] == k; j++ {
			k *= -1
		}
		if t := j - i + 1; t > 1 && ans < t {
			ans = t
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2778. 特殊元素平方和

简单1 种解法

标签：数组、枚举

题目、示例与约束

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

对 nums 中的元素 nums[i] 而言，如果 n 能够被 i 整除，即 n % i == 0 ，则认为 nums[i] 是一个 特殊元素 。

返回 nums 中所有 特殊元素 的 平方和 。

 

示例 1：

输入：nums = [1,2,3,4]
输出：21
解释：nums 中共有 3 个特殊元素：nums[1]，因为 4 被 1 整除；nums[2]，因为 4 被 2 整除；以及 nums[4]，因为 4 被 4 整除。 
因此，nums 中所有特殊元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[4] * nums[4] = 1 * 1 + 2 * 2 + 4 * 4 = 21 。  

示例 2：

输入：nums = [2,7,1,19,18,3]
输出：63
解释：nums 中共有 4 个特殊元素：nums[1]，因为 6 被 1 整除；nums[2] ，因为 6 被 2 整除；nums[3]，因为 6 被 3 整除；以及 nums[6]，因为 6 被 6 整除。 
因此，nums 中所有特殊元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[3] * nums[3] + nums[6] * nums[6] = 2 * 2 + 7 * 7 + 1 * 1 + 3 * 3 = 63 。 

 

提示：

• 1 <= nums.length == n <= 50
• 1 <= nums[i] <= 50

方法一：枚举 · Go 实现

思考

特殊元素是下标（从 $1$ 计）能整除 $n$ 的项，求它们的平方和。不必另开数组收集下标。

枚举 $i=1..n$，当 $nmodi=0$ 时把 $nums[i-1{]}^2$ 累加。

我们可以枚举数组中的每个元素，判断其是否为特殊元素，如果是则将其平方加入答案中。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func sumOfSquares(nums []int) (ans int) {
	n := len(nums)
	for i, x := range nums {
		if n%(i+1) == 0 {
			ans += x * x
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2798. 满足目标工作时长的员工数目

简单1 种解法

标签：数组

题目、示例与约束

公司里共有 n 名员工，按从 0 到 n - 1 编号。每个员工 i 已经在公司工作了 hours[i] 小时。

公司要求每位员工工作 至少 target 小时。

给你一个下标从 0 开始、长度为 n 的非负整数数组 hours 和一个非负整数 target 。

请你用整数表示并返回工作至少 target 小时的员工数。

 

示例 1：

输入：hours = [0,1,2,3,4], target = 2
输出：3
解释：公司要求每位员工工作至少 2 小时。
- 员工 0 工作 0 小时，不满足要求。
- 员工 1 工作 1 小时，不满足要求。
- 员工 2 工作 2 小时，满足要求。
- 员工 3 工作 3 小时，满足要求。
- 员工 4 工作 4 小时，满足要求。
共有 3 位满足要求的员工。

示例 2：

输入：hours = [5,1,4,2,2], target = 6
输出：0
解释：公司要求每位员工工作至少 6 小时。
共有 0 位满足要求的员工。

 

提示：

• 1 <= n == hours.length <= 50
• 0 <= hours[i], target <= 105

方法一：遍历计数 · Go 实现

思考

统计工作时长不小于 $target$ 的员工数。一次线性扫描即可，无需排序或额外结构。

对 $hours$ 中每个值判断 $x\ge target$ 并求和。

我们可以遍历数组 $hours$，对于每个员工，如果其工作时长 $x$ 大于等于 $target$，则将计数器 $ans$ 加一。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 是数组 $hours$ 的长度。空间复杂度 $O(1)$。

func numberOfEmployeesWhoMetTarget(hours []int, target int) (ans int) {
	for _, x := range hours {
		if x >= target {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2855. 使数组成为递增数组的最少右移次数

简单1 种解法

标签：数组

题目、示例与约束

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回让 nums 成为递增数组的 最少右移 次数，如果无法得到递增数组，返回 -1 。

一次 右移 指的是同时对所有下标进行操作，将下标为 i 的元素移动到下标 (i + 1) % n 处。

 

示例 1：

输入：nums = [3,4,5,1,2]
输出：2
解释：
第一次右移后，nums = [2,3,4,5,1] 。
第二次右移后，nums = [1,2,3,4,5] 。
现在 nums 是递增数组了，所以答案为 2 。

示例 2：

输入：nums = [1,3,5]
输出：0
解释：nums 已经是递增数组了，所以答案为 0 。

示例 3：

输入：nums = [2,1,4]
输出：-1
解释：无法将数组变为递增数组。

 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums 中的整数互不相同。

方法一：直接遍历 · Go 实现

思考

右移若干次后应成为严格递增。至多一处下降，且后半段须小于首元素。找到第一处下降后再扫描后半段，若能走到末尾，右移次数为 $n-i$。

我们先用一个指针 $i$ 从左到右遍历数组 $nums$，找出一段连续的递增序列，直到 $i$ 到达数组末尾或者 $nums[i-1]>nums[i]$。接下来我们用另一个指针 $k$ 从 $i+1$ 开始遍历数组 $nums$，找出一段连续的递增序列，直到 $k$ 到达数组末尾或者 $nums[k-1]>nums[k]$ 且 $nums[k]>nums[0]$。如果 $k$ 到达数组末尾，说明数组已经是递增的，返回 $n-i$；否则返回 $-1$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 是数组 $nums$ 的长度。

func minimumRightShifts(nums []int) int {
	n := len(nums)
	i := 1
	for i < n && nums[i-1] < nums[i] {
		i++
	}
	k := i + 1
	for k < n && nums[k-1] < nums[k] && nums[k] < nums[0] {
		k++
	}
	if k < n {
		return -1
	}
	return n - i
}

力扣原题 · Doocs 题解来源

2873. 有序三元组中的最大值 I

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

 

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。 

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

 

提示：

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 106

方法一：维护前缀最大值和最大差值 · Go 实现

思考

三元组值为 $(nums[i]-nums[j])\times nums[k]$ 且 $i<j<k$。 $n$ 虽小，仍可一次扫描：枚举 $k$ 时维护此前的最大值 $mx$ 与最大差值 $mx-nums[j]$，当前贡献即为该差值乘以 $nums[k]$。

我们用两个变量 $\mathit{\text{mx}}$ 和 $\mathit{\text{mxDiff}}$ 分别维护前缀最大值和最大差值，用一个变量 $\mathit{\text{ans}}$ 维护答案。初始时，这些变量都为 $0$。

接下来，我们枚举数组的每个元素 $x$ 作为 $\mathit{\text{nums}}[k]$，首先更新答案 $\mathit{\text{ans}}=max(\mathit{\text{ans}},\mathit{\text{mxDiff}}\times x)$，然后我们更新最大差值 $\mathit{\text{mxDiff}}=max(\mathit{\text{mxDiff}},\mathit{\text{mx}}-x)$，最后更新前缀最大值 $\mathit{\text{mx}}=max(\mathit{\text{mx}},x)$。

枚举完所有元素后，返回答案 $\mathit{\text{ans}}$。

时间复杂度 $O(n)$，其中 $n$ 是数组长度。空间复杂度 $O(1)$。

func maximumTripletValue(nums []int) int64 {
	ans, mx, mxDiff := 0, 0, 0
	for _, x := range nums {
		ans = max(ans, mxDiff*x)
		mxDiff = max(mxDiff, mx-x)
		mx = max(mx, x)
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2874. 有序三元组中的最大值 II

中等1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

 

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。 

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

 

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 106

方法一：维护前缀最大值和最大差值 · Go 实现

思考

与上一题公式相同而 $n$ 更大，三重枚举不可行。仍在一次扫描中维护前缀最大值与最大差值，按 $k$ 更新答案后再更新差值和最大值，保证下标顺序。

我们用两个变量 $\mathit{\text{mx}}$ 和 $\mathit{\text{mxDiff}}$ 分别维护前缀最大值和最大差值，用一个变量 $\mathit{\text{ans}}$ 维护答案。初始时，这些变量都为 $0$。

接下来，我们枚举数组的每个元素 $x$ 作为 $\mathit{\text{nums}}[k]$，首先更新答案 $\mathit{\text{ans}}=max(\mathit{\text{ans}},\mathit{\text{mxDiff}}\times x)$，然后我们更新最大差值 $\mathit{\text{mxDiff}}=max(\mathit{\text{mxDiff}},\mathit{\text{mx}}-x)$，最后更新前缀最大值 $\mathit{\text{mx}}=max(\mathit{\text{mx}},x)$。

枚举完所有元素后，返回答案 $\mathit{\text{ans}}$。

时间复杂度 $O(n)$，其中 $n$ 是数组长度。空间复杂度 $O(1)$。

func maximumTripletValue(nums []int) int64 {
	ans, mx, mxDiff := 0, 0, 0
	for _, x := range nums {
		ans = max(ans, mxDiff*x)
		mxDiff = max(mxDiff, mx-x)
		mx = max(mx, x)
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2899. 上一个遍历的整数

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个整数数组 nums ，其中 nums[i] 要么是一个正整数，要么是 -1 。我们需要为每个 -1 找到相应的正整数，我们称之为最后访问的整数。

为了达到这个目标，定义两个空数组：seen 和 ans。

从数组 nums 的头部开始遍历。

• 如果遇到正整数，把它添加到 seen 的 头部。
• 如果遇到 -1，则设 k 是到目前为止看到的 连续 -1 的数目(包括当前 -1)，
  • 如果 k 小于等于 seen 的长度，把 seen 的第 k 个元素添加到 ans。
  • 如果 k 严格大于 seen 的长度，把 -1 添加到 ans。

请你返回数组 ans。

 

示例 1：

输入：nums = [1,2,-1,-1,-1]
输出：[2,1,-1]
解释： 开始时 seen = [] 且 ans = []。
1.处理 nums[0]：nums 中的第一个元素是 1。我们将其放在 seen 的前面。现在，seen == [1]。
2.处理 nums[1]：下一个元素是 2。我们将其放在 seen 的前面。现在，seen == [2, 1]。
3.处理 nums[2]：下一个元素是 -1。这是 -1 的第一次出现，所以 k == 1。我们找到 seen 中的第一个元素，把 2 添加到 ans。现在，ans == [2]。
4.处理 nums[3]：又一个 -1。这是 -1 的第二次出现，所以 k == 2。seen 中的第二个元素是 1，所以我们把 1 添加到 ans。现在，ans == [2, 1]。
5.处理 nums[4]：又一个 -1。第三次出现，让 k = 3。然而，seen 中只有两个元素（[2, 1]）。因为 k 比 seen 中的元素数量更大，我们把 -1 添加到 ans。最终，ans == [2, 1, -1]。

示例 2：

输入：nums = [1,-1,2,-1,-1]
输出：[1,2,1]
解释： 开始时 seen = [] 且 ans = []。
1.处理 nums[0]：nums 中的第一个元素是 1。我们将其放在 seen 的前面。现在，seen == [1]。
2.处理 nums[1]：下一个元素是 -1。这是 -1 的第一次出现，所以 k == 1。我们找到 seen 中的第一个元素，即 1。把 1 添加到 ans。现在，ans == [1]。
3.处理 nums[2]：下一个元素是 2。我们将其放在 seen 的前面。现在，seen == [2, 1]。
4.处理 nums[3]：下一个元素是 -1。这个 -1 与 第一个 -1 不连续，因为中间有个 2。因此，k 重置为 1。seen 中的第一个元素是 2，所以我们把 2 添加到 ans。现在，ans == [1, 2]。
5.处理 nums[4]：又一个 -1。它与前一个 -1 相邻，所以 k == 2。seen 中的第 2 个元素是 1。把 1 添加到 ans。最终，ans == [1, 2, 1]。

 

提示：

• 1 <= nums.length <= 100
• nums[i] == -1 或 1 <= nums[i] <= 100

方法一：模拟 · Go 实现

思考

正整数按出现顺序记入 $seen$，连续的 $-1$ 表示取倒数第 $k$ 个已见表值。扫描时维护连续 $-1$ 的计数 $k$，遇正数则清零并追加；若 $k$ 超过 $seen$ 长度则记 $-1$。

我们直接根据题意模拟即可。

定义一个数组 $\mathit{\text{seen}}$ 来存储我们看到的正整数，定义一个数组 $\mathit{\text{ans}}$ 来存储答案。我们还需要一个变量 $k$ 来记录连续出现的 $-1$ 的数量。

我们遍历数组 $\mathit{\text{nums}}$：

• 如果当前元素 $x=-1$，我们将 $k$ 加 1。如果 $k$ 大于 $\mathit{\text{seen}}$ 的长度，我们在 $\mathit{\text{ans}}$ 中添加 $-1$；否则，我们在 $\mathit{\text{ans}}$ 中添加 $\mathit{\text{seen}}$ 的倒数第 $k$ 个元素。
• 如果当前元素 $x$ 是一个正整数，我们将 $k$ 重置为 0，并将 $x$ 添加到 $\mathit{\text{seen}}$ 的末尾。

时间复杂度 $O(n)$，空间复杂度 $O(n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。

func lastVisitedIntegers(nums []int) []int {
	seen := []int{}
	ans := []int{}
	k := 0

	for _, x := range nums {
		if x == -1 {
			k++
			if k > len(seen) {
				ans = append(ans, -1)
			} else {
				ans = append(ans, seen[len(seen)-k])
			}
		} else {
			k = 0
			seen = append(seen, x)
		}
	}

	return ans
}

力扣原题 · Doocs 题解来源

2908. 元素和最小的山形三元组 I

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

 

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为： 
- 1 < 3 < 5 
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

 

提示：

• 3 <= nums.length <= 50
• 1 <= nums[i] <= 50

方法一：预处理 + 枚举 · Go 实现

思考

山形要求 $i<j<k$ 且 $nums[i]<nums[j]>nums[k]$，目标和最小。 $n\le 50$，三重循环可行。固定峰顶 $j$ 后，真正需要的只是左侧最小值与右侧最小值，前提是二者都严格小于 $nums[j]$。

为此先预处理 $right[i]$ 为后缀最小值，再从左扫描同时维护 $left$。对每个峰顶检验两侧是否更小，并更新三数之和。不存在则返回 $-1$。

我们可以预处理出每个位置右侧的最小值，记录在数组 $right[i]$ 中，即 $right[i]$ 表示 $nums[i+1..n-1]$ 中的最小值。

接下来，我们从左到右枚举山形三元组的中间元素 $nums[i]$，用一个变量 $left$ 表示 $nums[0..i-1]$ 中的最小值，用一个变量 $ans$ 表示当前找到的最小元素和。对于每个 $i$，我们需要找到满足 $left<nums[i]$ 且 $right[i+1]<nums[i]$ 的元素 $nums[i]$，并更新 $ans$。

最后，如果 $ans$ 仍然为初始值，则说明不存在山形三元组，返回 $-1$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

func minimumSum(nums []int) int {
	n := len(nums)
	const inf = 1 << 30
	right := make([]int, n+1)
	right[n] = inf
	for i := n - 1; i >= 0; i-- {
		right[i] = min(right[i+1], nums[i])
	}
	ans, left := inf, inf
	for i, x := range nums {
		if left < x && right[i+1] < x {
			ans = min(ans, left+x+right[i+1])
		}
		left = min(left, x)
	}
	if ans == inf {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

2923. 找到冠军 I

简单1 种解法

标签：数组、矩阵

题目、示例与约束

一场比赛中共有 n 支队伍，按从 0 到  n - 1 编号。

给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j ：如果 grid[i][j] == 1，那么 i 队比 j 队 强 ；否则，j 队比 i 队 强 。

在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。

返回这场比赛中将会成为冠军的队伍。

 

示例 1：

输入：grid = [[0,1],[0,0]]
输出：0
解释：比赛中有两支队伍。
grid[0][1] == 1 表示 0 队比 1 队强。所以 0 队是冠军。

示例 2：

输入：grid = [[0,0,1],[1,0,1],[0,0,0]]
输出：1
解释：比赛中有三支队伍。
grid[1][0] == 1 表示 1 队比 0 队强。
grid[1][2] == 1 表示 1 队比 2 队强。
所以 1 队是冠军。

 

提示：

• n == grid.length
• n == grid[i].length
• 2 <= n <= 100
• grid[i][j] 的值为 0 或 1
• 对于所有 i， grid[i][i] 等于 0.
• 对于满足 i != j 的所有 i, j ，grid[i][j] != grid[j][i] 均成立
• 生成的输入满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强

方法一：枚举 · Go 实现

思考

$grid$ 是完全的胜负关系且具有传递性，冠军即击败其余所有队伍的那一支。 $n\le 100$，枚举每行检查除对角线外是否全为 $1$ 即可。

输入保证存在唯一冠军，因此找到第一支满足条件的队伍便可返回。无需建图或计算入度。

我们可以枚举每一支队伍 $i$，如果 $i$ 队的每一场比赛都赢了，那么 $i$ 队就是冠军，直接返回 $i$ 即可。

时间复杂度 $O(n^2)$，其中 $n$ 是队伍数量。空间复杂度 $O(1)$。

func findChampion(grid [][]int) int {
	n := len(grid)
	for i := 0; ; i++ {
		cnt := 0
		for j, x := range grid[i] {
			if i != j && x == 1 {
				cnt++
			}
		}
		if cnt == n-1 {
			return i
		}
	}
}

力扣原题 · Doocs 题解来源

2934. 最大化数组末位元素的最少操作次数

中等1 种解法

标签：数组、枚举

题目、示例与约束

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，这两个数组的长度都是 n 。

你可以执行一系列 操作（可能不执行）。

在每次操作中，你可以选择一个在范围 [0, n - 1] 内的下标 i ，并交换 nums1[i] 和 nums2[i] 的值。

你的任务是找到满足以下条件所需的 最小 操作次数：

• nums1[n - 1] 等于 nums1 中所有元素的 最大值 ，即 nums1[n - 1] = max(nums1[0], nums1[1], ..., nums1[n - 1]) 。
• nums2[n - 1] 等于 nums2 中所有元素的 最大值 ，即 nums2[n - 1] = max(nums2[0], nums2[1], ..., nums2[n - 1]) 。

以整数形式，表示并返回满足上述 全部 条件所需的 最小 操作次数，如果无法同时满足两个条件，则返回 -1 。

 

示例 1：

输入：nums1 = [1,2,7]，nums2 = [4,5,3]
输出：1
解释：在这个示例中，可以选择下标 i = 2 执行一次操作。
交换 nums1[2] 和 nums2[2] 的值，nums1 变为 [1,2,3] ，nums2 变为 [4,5,7] 。
同时满足两个条件。
可以证明，需要执行的最小操作次数为 1 。
因此，答案是 1 。

示例 2：

输入：nums1 = [2,3,4,5,9]，nums2 = [8,8,4,4,4]
输出：2
解释：在这个示例中，可以执行以下操作：
首先，选择下标 i = 4 执行操作。
交换 nums1[4] 和 nums2[4] 的值，nums1 变为 [2,3,4,5,4] ，nums2 变为 [8,8,4,4,9] 。
然后，选择下标 i = 3 执行操作。
交换 nums1[3] 和 nums2[3] 的值，nums1 变为 [2,3,4,4,4] ，nums2 变为 [8,8,4,5,9] 。
同时满足两个条件。 
可以证明，需要执行的最小操作次数为 2 。 
因此，答案是 2 。

示例 3：

输入：nums1 = [1,5,4]，nums2 = [2,5,3]
输出：-1
解释：在这个示例中，无法同时满足两个条件。
因此，答案是 -1 。

 

提示：

• 1 <= n == nums1.length == nums2.length <= 1000
• 1 <= nums1[i] <= 109
• 1 <= nums2[i] <= 109

方法一：分情况讨论 + 贪心 · Go 实现

思考

最终要 $nums1$ 的最大值在末尾、 $nums2$ 的最大值在末尾，且只能交换同下标。末尾一对要么保持、要么交换一次，两种终态决定了前面每一对应当如何摆放。

函数 $f(x,y)$ 假定末尾已是 $(x,y)$，对前 $n-1$ 对：已满足则不动，对调后才满足则交换，否则无解。答案在「不换末尾」与「换末尾再加 $1$」中取可行的较小值。

我们可以分成两种情况讨论：

1. 不交换 $nums1[n-1]$ 和 $nums2[n-1]$ 的值
2. 交换 $nums1[n-1]$ 和 $nums2[n-1]$ 的值

对于每一种情况，我们记数组 $nums1$ 和 $nums2$ 的最后一个值分别为 $x$ 和 $y$。然后遍历数组 $nums1$ 和 $nums2$ 的前 $n-1$ 个值，用一个变量 $cnt$ 记录交换次数。如果 $nums1[i]\le x$ 且 $nums2[i]\le y$，则不需要交换，否则如果 $nums1[i]\le y$ 且 $nums2[i]\le x$，则需要交换，否则无法同时满足两个条件，返回 $-1$。最后返回 $cnt$ 即可。

我们记两种情况的交换次数分别为 $a$ 和 $b$，如果 $a+b=-2$，则无法同时满足两个条件，返回 $-1$，否则返回 $min(a,b+1)$。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

func minOperations(nums1 []int, nums2 []int) int {
	n := len(nums1)
	f := func(x, y int) (cnt int) {
		for i, a := range nums1[:n-1] {
			b := nums2[i]
			if a <= x && b <= y {
				continue
			}
			if !(a <= y && b <= x) {
				return -1
			}
			cnt++
		}
		return
	}
	a, b := f(nums1[n-1], nums2[n-1]), f(nums2[n-1], nums1[n-1])
	if a+b == -2 {
		return -1
	}
	return min(a, b+1)
}

力扣原题 · Doocs 题解来源

2951. 找出峰值

简单1 种解法

标签：数组、枚举

题目、示例与约束

给你一个下标从 0 开始的数组 mountain 。你的任务是找出数组 mountain 中的所有 峰值。

以数组形式返回给定数组中 峰值 的下标，顺序不限 。

注意：

• 峰值 是指一个严格大于其相邻元素的元素。
• 数组的第一个和最后一个元素 不 是峰值。

 

示例 1：

输入：mountain = [2,4,4]
输出：[]
解释：mountain[0] 和 mountain[2] 不可能是峰值，因为它们是数组的第一个和最后一个元素。
mountain[1] 也不可能是峰值，因为它不严格大于 mountain[2] 。
因此，答案为 [] 。

示例 2：

输入：mountain = [1,4,3,8,5]
输出：[1,3]
解释：mountain[0] 和 mountain[4] 不可能是峰值，因为它们是数组的第一个和最后一个元素。
mountain[2] 也不可能是峰值，因为它不严格大于 mountain[3] 和 mountain[1] 。
但是 mountain[1] 和 mountain[3] 严格大于它们的相邻元素。
因此，答案是 [1,3] 。

 

提示：

• 3 <= mountain.length <= 100
• 1 <= mountain[i] <= 100

方法一：直接遍历 · Go 实现

思考

峰值定义为两侧都严格更小的内部下标。 $n\le 100$，从 $1$ 扫到 $n-2$ 比较三元组即可。

两端依题意不是峰值，无需特判边界以外的情况。

我们直接遍历下标 $i\in [1,n-2]$，对于每个下标 $i$，如果满足 $mountain[i-1]<mountain[i]$ 并且 $mountain[i+1]<mountain[i]$，那么 $mountain[i]$ 就是一个峰值，我们将下标 $i$ 加入答案数组中。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func findPeaks(mountain []int) (ans []int) {
	for i := 1; i < len(mountain)-1; i++ {
		if mountain[i-1] < mountain[i] && mountain[i+1] < mountain[i] {
			ans = append(ans, i)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2960. 统计已测试设备

简单1 种解法

标签：数组、计数、模拟

题目、示例与约束

给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。

你的任务是按照顺序测试每个设备 i，执行以下测试操作：

• 如果 batteryPercentages[i] 大于 0：
  • 增加 已测试设备的计数。
  • 将下标 j 在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。
  • 移动到下一个设备。
• 否则，移动到下一个设备而不执行任何测试。

返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。

 

示例 1：

输入：batteryPercentages = [1,1,2,1,3]
输出：3
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [1,0,1,0,2] 。
在设备 1 上，batteryPercentages[1] == 0 ，移动到下一个设备而不进行测试。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 变为 [1,0,1,0,1] 。
在设备 3 上，batteryPercentages[3] == 0 ，移动到下一个设备而不进行测试。
在设备 4 上，batteryPercentages[4] > 0 ，现在有 3 个已测试设备，batteryPercentages 保持不变。
因此，答案是 3 。

示例 2：

输入：batteryPercentages = [0,1,2]
输出：2
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] == 0 ，移动到下一个设备而不进行测试。
在设备 1 上，batteryPercentages[1] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [0,1,1] 。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 保持不变。
因此，答案是 2 。

 

提示：

• 1 <= n == batteryPercentages.length <= 100
• 0 <= batteryPercentages[i] <= 100

方法一：模拟 · Go 实现

思考

测试一台电量仍为正的设备后，其后所有设备电量减 $1$。已测台数 $ans$ 恰等于该设备之前被减去的总量，故电量 $x$ 能被测试当且仅当 $x>ans$。

$n\le 100$，扫描累加布尔值即可，不必修改数组。

假设我们当前已测试的设备数量为 $ans$，当测试新的一台设备 $i$ 时，它的剩余电量为 $max(0,batteryPercentages[i]-ans)$，如果剩余电量大于 $0$，则说明这台设备可以进行测试，此时我们需要将 $ans$ 增加 $1$。

最后返回 $ans$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

func countTestedDevices(batteryPercentages []int) (ans int) {
	for _, x := range batteryPercentages {
		if x > ans {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3000. 对角线最长的矩形的面积

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 dimensions。

对于所有下标 i（0 <= i < dimensions.length），dimensions[i][0] 表示矩形 i 的长度，而 dimensions[i][1] 表示矩形 i 的宽度。

返回对角线最 长 的矩形的 面积 。如果存在多个对角线长度相同的矩形，返回其中面积最 大 的矩形的面积。

 

示例 1：

输入：dimensions = [[9,3],[8,6]]
输出：48
解释：
下标 = 0，长度 = 9，宽度 = 3。对角线长度 = sqrt(9 * 9 + 3 * 3) = sqrt(90) ≈ 9.487。
下标 = 1，长度 = 8，宽度 = 6。对角线长度 = sqrt(8 * 8 + 6 * 6) = sqrt(100) = 10。
因此，下标为 1 的矩形对角线更长，所以返回面积 = 8 * 6 = 48。

示例 2：

输入：dimensions = [[3,4],[4,3]]
输出：12
解释：两个矩形的对角线长度相同，为 5，所以最大面积 = 12。

 

提示：

• 1 <= dimensions.length <= 100
• dimensions[i].length == 2
• 1 <= dimensions[i][0], dimensions[i][1] <= 100

方法一：数学 · Go 实现

思考

矩形数量不超过 $100$，枚举所有矩形并比较对角线与面积均可在线性时间内完成。直接对对角线开方再比较，会引入浮点误差。

对角线长短只取决于 $l^2+w^2$，面积则是 $l\times w$。若某矩形的平方和更大，则它独占最长对角线；若平方和相同，则应在这些矩形中取面积最大者。

为此只需一遍扫描，维护当前最大平方和 $\mathit{\text{mx}}$ 以及对应面积 $\mathit{\text{ans}}$。平方和更新时改写面积，相等时对面积取最大值。

根据勾股定理，矩形的对角线的平方为 $l^2+w^2$，其中 $l$ 和 $w$ 分别是矩形的长度和宽度。

我们可以遍历所有矩形，计算它们的对角线长度的平方，并记录下最大的对角线长度和对应的面积。

遍历结束后，我们返回记录的最大面积。

时间复杂度 $O(n)$，其中 $n$ 是矩形的数量。空间复杂度 $O(1)$。

func areaOfMaxDiagonal(dimensions [][]int) (ans int) {
	mx := 0
	for _, d := range dimensions {
		l, w := d[0], d[1]
		t := l*l + w*w
		if mx < t {
			mx = t
			ans = l * w
		} else if mx == t {
			ans = max(ans, l*w)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3030. 找出网格的区域平均强度

中等1 种解法

标签：数组、矩阵

题目、示例与约束

给你一个下标从 0 开始、大小为 m x n 的网格 image ，表示一个灰度图像，其中 image[i][j] 表示在范围 [0..255] 内的某个像素强度。另给你一个 非负 整数 threshold 。

如果 image[a][b] 和 image[c][d] 满足 |a - c| + |b - d| == 1 ，则称这两个像素是 相邻像素 。

区域 是一个 3 x 3 的子网格，且满足区域中任意两个 相邻 像素之间，像素强度的 绝对差 小于或等于 threshold 。

区域 内的所有像素都认为属于该区域，而一个像素 可以 属于 多个 区域。

你需要计算一个下标从 0 开始、大小为 m x n 的网格 result ，其中 result[i][j] 是 image[i][j] 所属区域的 平均 强度，向下取整 到最接近的整数。如果 image[i][j] 属于多个区域，result[i][j] 是这些区域的 “取整后的平均强度” 的 平均值，也 向下取整 到最接近的整数。如果 image[i][j] 不属于任何区域，则 result[i][j] 等于 image[i][j] 。

返回网格 result 。

 

示例 1：

输入：image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3
输出：[[9,9,9,9],[9,9,9,9],[9,9,9,9]]
解释：图像中存在两个区域，如图片中的阴影区域所示。第一个区域的平均强度为 9 ，而第二个区域的平均强度为 9.67 ，向下取整为 9 。两个区域的平均强度为 (9 + 9) / 2 = 9 。由于所有像素都属于区域 1 、区域 2 或两者，因此 result 中每个像素的强度都为 9 。
注意，在计算多个区域的平均值时使用了向下取整的值，因此使用区域 2 的平均强度 9 来进行计算，而不是 9.67 。

示例 2：

输入：image = [[10,20,30],[15,25,35],[20,30,40],[25,35,45]], threshold = 12
输出：[[25,25,25],[27,27,27],[27,27,27],[30,30,30]]
解释：图像中存在两个区域，如图片中的阴影区域所示。第一个区域的平均强度为 25 ，而第二个区域的平均强度为 30 。两个区域的平均强度为 (25 + 30) / 2 = 27.5 ，向下取整为 27 。图像中第 0 行的所有像素属于区域 1 ，因此 result 中第 0 行的所有像素为 25 。同理，result 中第 3 行的所有像素为 30 。图像中第 1 行和第 2 行的像素属于区域 1 和区域 2 ，因此它们在 result 中的值为 27 。

示例 3：

输入：image = [[5,6,7],[8,9,10],[11,12,13]], threshold = 1
输出：[[5,6,7],[8,9,10],[11,12,13]]
解释：图像中不存在任何区域，因此对于所有像素，result[i][j] == image[i][j] 。

 

提示：

• 3 <= n, m <= 500
• 0 <= image[i][j] <= 255
• 0 <= threshold <= 255

方法一 · Go 实现

思考

每个 $3\times 3$ 区域在相邻差不超过阈值时成为合法区域，格子取所有覆盖它的区域平均值。 $n,m\le 500$，枚举所有区域为 $O(nm)$。

区域是否合法只取决于内部 $12$ 条邻边。合法则把九格均值累加到结果，并给覆盖计数加一。

最后对每个格子：计数为零则保留原值，否则用累加和除以计数。

func resultGrid(image [][]int, threshold int) [][]int {
	n := len(image)
	m := len(image[0])
	ans := make([][]int, n)
	ct := make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, m)
		ct[i] = make([]int, m)
	}
	for i := 0; i+2 < n; i++ {
		for j := 0; j+2 < m; j++ {
			region := true
			for k := 0; k < 3; k++ {
				for l := 0; l < 2; l++ {
					region = region && abs(image[i+k][j+l]-image[i+k][j+l+1]) <= threshold
				}
			}
			for k := 0; k < 2; k++ {
				for l := 0; l < 3; l++ {
					region = region && abs(image[i+k][j+l]-image[i+k+1][j+l]) <= threshold
				}
			}
			if region {
				tot := 0
				for k := 0; k < 3; k++ {
					for l := 0; l < 3; l++ {
						tot += image[i+k][j+l]
					}
				}
				for k := 0; k < 3; k++ {
					for l := 0; l < 3; l++ {
						ct[i+k][j+l]++
						ans[i+k][j+l] += tot / 9
					}
				}
			}
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if ct[i][j] == 0 {
				ans[i][j] = image[i][j]
			} else {
				ans[i][j] /= ct[i][j]
			}
		}
	}
	return ans
}
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

3033. 修改矩阵

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给你一个下标从 0 开始、大小为 m x n 的整数矩阵 matrix ，新建一个下标从 0 开始、名为 answer 的矩阵。使 answer 与 matrix 相等，接着将其中每个值为 -1 的元素替换为所在列的 最大 元素。

返回矩阵 answer 。

 

示例 1：

输入：matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
输出：[[1,2,9],[4,8,6],[7,8,9]]
解释：上图显示了发生替换的元素（蓝色区域）。
- 将单元格 [1][1] 中的值替换为列 1 中的最大值 8 。
- 将单元格 [0][2] 中的值替换为列 2 中的最大值 9 。

示例 2：

输入：matrix = [[3,-1],[5,2]]
输出：[[3,2],[5,2]]
解释：上图显示了发生替换的元素（蓝色区域）。

 

提示：

• m == matrix.length
• n == matrix[i].length
• 2 <= m, n <= 50
• -1 <= matrix[i][j] <= 100
• 测试用例中生成的输入满足每列至少包含一个非负整数。

方法一：模拟 · Go 实现

思考

把矩阵中的 $-1$ 换成所在列的最大值。行列不超过 $50$，按列扫描两次即可。

每列的最大值与替换互不干扰，先求列最大再写回 $-1$ 位置。

我们可以根据题目描述，遍历每一列，找到每一列的最大值，然后再遍历每一列，将值为 -1 的元素替换为该列的最大值。

时间复杂度 $O(m\times n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$。

func modifiedMatrix(matrix [][]int) [][]int {
	m, n := len(matrix), len(matrix[0])
	for j := 0; j < n; j++ {
		mx := -1
		for i := 0; i < m; i++ {
			mx = max(mx, matrix[i][j])
		}
		for i := 0; i < m; i++ {
			if matrix[i][j] == -1 {
				matrix[i][j] = mx
			}
		}
	}
	return matrix
}

力扣原题 · Doocs 题解来源

3038. 相同分数的最大操作数目 I

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作：

• 选择 nums 中的前两个元素并将它们删除。

一次操作的 分数 是被删除元素的和。

在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。

请你返回按照上述要求 最多 可以进行的操作次数。

 

示例 1：

输入：nums = [3,2,1,4,5]
输出：2
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,4,5] 。
- 删除前两个元素，分数为 1 + 4 = 5 ，nums = [5] 。
由于只剩下 1 个元素，我们无法继续进行任何操作。

示例 2：

输入：nums = [3,2,6,1,4]
输出：1
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
由于下一次操作的分数与前一次不相等，我们无法继续进行任何操作。

 

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 1000

方法一：遍历 · Go 实现

思考

每次只能取最前面两个数，分数必须与第一次相同。 $n\le 100$，按规则模拟即可。

第一次的和 $s$ 固定了后续每一次操作。一旦不足两个元素或和不为 $s$ 就停止。

按下标步长 $2$ 扫描并计数。

我们先计算前两个元素的和，记为 $s$，然后遍历数组，每次操作取两个元素，如果和不等于 $s$，则停止遍历。最后返回操作次数即可。

时间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。

func maxOperations(nums []int) (ans int) {
	s, n := nums[0]+nums[1], len(nums)
	for i := 0; i+1 < n && nums[i]+nums[i+1] == s; i += 2 {
		ans++
	}
	return
}

力扣原题 · Doocs 题解来源

3065. 超过阈值的最少操作数 I

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你可以删除 nums 中的最小元素。

你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。

 

示例 1：

输入：nums = [2,11,10,1,3], k = 10
输出：3
解释：第一次操作后，nums 变为 [2, 11, 10, 3] 。
第二次操作后，nums 变为 [11, 10, 3] 。
第三次操作后，nums 变为 [11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 3 。

示例 2：

输入：nums = [1,1,2,4,9], k = 1
输出：0
解释：数组中的所有元素都大于等于 1 ，所以不需要对 nums 做任何操作。

示例 3：

输入：nums = [1,1,2,4,9], k = 9
输出：4
解释：nums 中只有一个元素大于等于 9 ，所以需要执行 4 次操作。

 

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 109
• 1 <= k <= 109
• 输入保证至少有一个满足 nums[i] >= k 的下标 i 存在。

方法一：遍历计数 · Go 实现

思考

每次删除一个小于 $k$ 的数，问最少几次使所有剩余数 $\ge k$。删除顺序不影响次数。

答案即小于 $k$ 的元素个数。一遍计数即可。

我们只需要遍历一遍数组，统计小于 $k$ 的元素个数即可。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

func minOperations(nums []int, k int) (ans int) {
	for _, x := range nums {
		if x < k {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3073. 最大递增三元组 🔒

中等1 种解法

标签：数组、有序集合

题目、示例与约束

给定一个数组 nums，返回满足 i < j < k 且 nums[i] < nums[j] < nums[k] 的三元组 (i, j, k)  的 最大值。

三元组 (i, j, k)  的 值 为 nums[i] - nums[j] + nums[k]。

 

 

示例 1:

输入：nums = [5,6,9]
输出：8
解释：对于一个递增的三元组，我们只有一个选择，那就是选择所有三个元素。三元组的值为 5 - 6 + 9 = 8。

示例 2:

输入：nums = [1,5,3,6]
输出：4
解释：只有两个递增三元组：
(0, 1, 3)：这个三元组的值为 nums[0] - nums[1] + nums[3] = 1 - 5 + 6 = 2。
(0, 2, 3)：这个三元组的值为 nums[0] - nums[2] + nums[3] = 1 - 3 + 6 = 4。
因此答案是 4。

 

提示:

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 输入数据保证至少一个三元组满足给定条件。

方法一：后缀最大值 + 有序集合 · Go 实现

思考

求 $i<j<k$ 且 $nums[i]<nums[j]<nums[k]$ 时 $nums[i]-nums[j]+nums[k]$ 的最大。 $n\le {10}^5$。

固定 $j$ 后， $k$ 应取右侧最大值（且须大于 $nums[j]$）， $i$ 应取左侧小于 $nums[j]$ 的最大值。

预计算后缀最大，左侧用有序集合动态插入，二分出小于 $nums[j]$ 的最大元。

我们不妨考虑枚举 $nums[j]$，那么我们需要在 $j$ 的左侧找到一个最大的 $nums[i]$，使得 $nums[i]<nums[j]$，并且在 $j$ 的右侧找到一个最大的 $nums[k]$，使得 $nums[k]>nums[j]$。

因此，我们可以预处理出数组 $right$，其中 $right[i]$ 表示 $nums[i]$ 右侧的最大值。然后我们可以使用有序集合来维护 $nums[j]$ 左侧的值，这样我们就可以在 $O(\log n)$ 的时间内找到最大的小于 $nums[j]$ 的 $nums[i]$。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

func maximumTripletValue(nums []int) (ans int) {
	n := len(nums)
	right := make([]int, n)
	right[n-1] = nums[n-1]
	for i := n - 2; i >= 0; i-- {
		right[i] = max(nums[i], right[i+1])
	}
	ts := treemap.NewWithIntComparator()
	ts.Put(nums[0], nil)
	for j := 1; j < n-1; j++ {
		if right[j+1] > nums[j] {
			val, _ := ts.Floor(nums[j] - 1)
			if val != nil {
				ans = max(ans, val.(int)-nums[j]+right[j+1])
			}
		}
		ts.Put(nums[j], nil)
	}
	return
}

力扣原题 · Doocs 题解来源

3105. 最长的严格递增或递减子数组

简单1 种解法

标签：数组

题目、示例与约束

给你一个整数数组 nums 。

返回数组 nums 中 严格递增 或 严格递减 的最长非空子数组的长度。

 

示例 1：

输入：nums = [1,4,3,3,2]

输出：2

解释：

nums 中严格递增的子数组有[1]、[2]、[3]、[3]、[4] 以及 [1,4] 。

nums 中严格递减的子数组有[1]、[2]、[3]、[3]、[4]、[3,2] 以及 [4,3] 。

因此，返回 2 。

示例 2：

输入：nums = [3,3,3,3]

输出：1

解释：

nums 中严格递增的子数组有 [3]、[3]、[3] 以及 [3] 。

nums 中严格递减的子数组有 [3]、[3]、[3] 以及 [3] 。

因此，返回 1 。

示例 3：

输入：nums = [3,2,1]

输出：3

解释：

nums 中严格递增的子数组有 [3]、[2] 以及 [1] 。

nums 中严格递减的子数组有 [3]、[2]、[1]、[3,2]、[2,1] 以及 [3,2,1] 。

因此，返回 3 。

 

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

方法一：两次遍历 · Go 实现

思考

所求为严格递增或严格递减的最长连续段。一次扫描中同时维护两种方向，需要在转折处仔细重置，实现容易混淆。

$n$ 的规模允许两次线性遍历。递增段与递减段彼此独立，分开统计后再取较大值即可。

因此先扫一遍累计严格上升长度，再扫一遍累计严格下降长度，各自在破坏单调处重置为 $1$。两次遍历的较大值即为答案。

我们先进行一次遍历，找出严格递增的最长子数组长度，更新答案。然后再进行一次遍历，找出严格递减的最长子数组长度，再次更新答案。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func longestMonotonicSubarray(nums []int) int {
	ans := 1
	t := 1
	for i, x := range nums[1:] {
		if nums[i] < x {
			t++
			ans = max(ans, t)
		} else {
			t = 1
		}
	}
	t = 1
	for i, x := range nums[1:] {
		if nums[i] > x {
			t++
			ans = max(ans, t)
		} else {
			t = 1
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

3127. 构造相同颜色的正方形

简单1 种解法

标签：数组、枚举、矩阵

题目、示例与约束

给你一个二维 3 x 3 的矩阵 grid ，每个格子都是一个字符，要么是 'B' ，要么是 'W' 。字符 'W' 表示白色，字符 'B' 表示黑色。

你的任务是改变 至多一个 格子的颜色，使得矩阵中存在一个 2 x 2 颜色完全相同的正方形。

如果可以得到一个相同颜色的 2 x 2 正方形，那么返回 true ，否则返回 false 。

 

示例 1：

 

 

 

 

 

 

 

 

 

输入：grid = [["B","W","B"],["B","W","W"],["B","W","B"]]

输出：true

解释：

修改 grid[0][2] 的颜色，可以满足要求。

示例 2：

 

 

 

 

 

 

 

 

 

输入：grid = [["B","W","B"],["W","B","W"],["B","W","B"]]

输出：false

解释：

只改变一个格子颜色无法满足要求。

示例 3：

 

 

 

 

 

 

 

 

 

输入：grid = [["B","W","B"],["B","W","W"],["B","W","W"]]

输出：true

解释：

grid 已经包含一个 2 x 2 颜色相同的正方形了。

 

提示：

• grid.length == 3
• grid[i].length == 3
• grid[i][j] 要么是 'W' ，要么是 'B' 。

方法一：枚举 · Go 实现

思考

网格固定为 $3\times 3$，一次改色后须出现同色 $2\times 2$。枚举改哪个格子再检查，情况虽少但比直接看每个 $2\times 2$ 更绕。

一个 $2\times 2$ 已有三格同色时，一次修改即可补齐；四格已经同色则无需修改。等价于该窗内黑白个数不等。

因此枚举四个可能的 $2\times 2$，统计 W 与 B，一旦不等即可返回真。网格尺寸为常数。

我们可以枚举每个 $2\times 2$ 的正方形，统计黑色和白色的个数，如果两者个数不相等，那么就可以构造一个相同颜色的正方形，返回 true。

否则，遍历结束后返回 false。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

func canMakeSquare(grid [][]byte) bool {
	dirs := [5]int{0, 0, 1, 1, 0}
	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			cnt1, cnt2 := 0, 0
			for k := 0; k < 4; k++ {
				x, y := i+dirs[k], j+dirs[k+1]
				if grid[x][y] == 'W' {
					cnt1++
				} else {
					cnt2++
				}
			}
			if cnt1 != cnt2 {
				return true
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源