当前位置：首页 > news >正文

每日一题力扣 3418. 机器人可以获得的最大金币数力扣 215. 数组中的第K个最大元素动态规划 TopK问题 C++ 题解

news 2026/6/13 4:14:15

文章目录

力扣 3418. 机器人可以获得的最大金币数
- 题目描述
- 思路简介
- 代码实现
- 复杂度分析
力扣 215. 数组中的第K个最大元素
- 题目描述
- 思路简介
- 代码实现
- 复杂度分析
踩坑记录

力扣 3418. 机器人可以获得的最大金币数

题目描述

力扣 3418. 机器人可以获得的最大金币数

示例 1：
输入： coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
输出： 8
解释：
一个获得最多金币的最优路径如下：
从 (0, 0) 出发，初始金币为 0（总金币 = 0）。
移动到 (0, 1)，获得 1 枚金币（总金币 = 0 + 1 = 1）。
移动到 (1, 1)，遇到强盗抢走 2 枚金币。机器人在此处使用一次感化能力，避免被抢（总金币 = 1）。
移动到 (1, 2)，获得 3 枚金币（总金币 = 1 + 3 = 4）。
移动到 (2, 2)，获得 4 枚金币（总金币 = 4 + 4 = 8）。

示例 2：
输入： coins = [[10,10,10],[10,10,10]]
输出： 40
解释：
一个获得最多金币的最优路径如下：
从 (0, 0) 出发，初始金币为 10（总金币 = 10）。
移动到 (0, 1)，获得 10 枚金币（总金币 = 10 + 10 = 20）。
移动到 (0, 2)，再获得 10 枚金币（总金币 = 20 + 10 = 30）。
移动到 (1, 2)，获得 10 枚金币（总金币 = 30 + 10 = 40）。

提示：
m == coins.length
n == coins[i].length
1 <= m, n <= 500
-1000 <= coins[i][j] <= 1000

思路简介

这道题是典型的带状态约束的网格动态规划问题。机器人只能向右或向下移动，核心约束是最多可使用2次感化能力，因此无法用常规的二维DP解决，需要引入第三个维度记录感化能力的使用次数。

我们设已知的金币数组大小m,n，为了规避网格边界（第一行、第一列）的特殊初始化处理，我们将DP数组的维度定义为(m+1) x (n+1) x 3，其中：
dp[i][j][k]表示机器人从起点(0,0)走到网格单元格(i-1,j-1)时，累计使用了k次感化能力，能够获得的最大金币数（k的取值为0、1、2，对应0次、1次、2次感化）。

状态转移方程推导

机器人到达(i-1,j-1)只有两种路径：从上方(i-2,j-1)向下走，或从左方(i-1,j-2)向右走。针对当前单元格是否使用感化能力，分两种情况处理：

k=0（未使用过感化能力）
此时无法对当前单元格使用感化，只能直接累加当前单元格的金币值。取上方和左方路径中的最大值，加上当前单元格的金币即可：
dp[i][j][0] = max(dp[i-1][j][0], dp[i][j-1][0]) + coins[i-1][j-1]
1≤k≤2（已使用k次感化能力）
此时有两种选择，取两者的最优解：
- 选择1：当前单元格不使用感化：逻辑和k=0一致，感化次数保持k不变，累加当前单元格金币。
- 选择2：当前单元格使用感化：coins[i][j] < 0的单元格才有强盗也就是这种单元格刚才会进入当前情况，即当前单元格中负数单元格不扣钱，收益为 0，所以我们直接去找上方和左方（dp[i-1][j], dp[i][j-1]）的k-1时（当前为k那么使用本次感化前的使用次数为k-1）的最大值即可。

最终状态转移方程：

dp[i][j][k]=max(max(dp[i-1][j][k],dp[i][j-1][k])+coins[i-1][j-1],// 不使用感化max(dp[i-1][j][k-1],dp[i][j-1][k-1])// 使用感化，当前单元格无金币损失)

注：当当前单元格为正数时，「不使用感化」的收益一定更高，因此选择2会自动被舍弃，无需额外判断。

初始化逻辑
对dp数组的初始化用的是INT_MIN/2而不是INT_MIN是因为：

INT_MIN是 int 类型的最小值（-2^31），后续状态转移时如果加上负数，会触发整型溢出，导致未定义行为，除以 2 可以留出足够的数值余量，避免溢出。

起点(0,0)对应DP数组的dp[1][1][k]，分情况初始化：

dp[1][1][0]：不使用感化，直接获取起点的金币值，即coins[0][0]。
dp[1][1][1]、dp[1][1][2]：使用感化能力（哪怕起点是负数，也能避免扣钱），因此收益为max(coins[0][0], 0)。

由于题目并没有说明，所以起点的值不一定为固定值，所以我们的初始化不能够合并成一个循环进行

最终结果
题目允许最多使用2次感化能力，因此最终结果为dp[m][n][2]。

dp[m][n][2]：(0,0)~(m-1,n-1)这个范围中用了2次感化技能之后取得的最大金币数量

为什么直接返回dp[m][n][2]，而不是max(dp[m][n][0], dp[m][n][1], dp[m][n][2])—— 因为感化次数越多，可选的操作越多，最优收益一定满足dp[m][n][2] >= dp[m][n][1] >= dp[m][n][0]

代码实现

#include<vector>#include<climits>// 用于INT_MINusingnamespacestd;classSolution{public:intmaximumAmount(vector<vector<int>>&coins){intm=coins.size();// 网格的行数intn=coins[0].size();// 网格的列数// 定义三维DP数组，维度为(m+1) x (n+1) x 3// 初始化为INT_MIN/2，代表初始状态不可达// 除以2是为了避免后续状态转移时，加上负数导致整型溢出vector<vector<vector<int>>>dp(m+1,vector<vector<int>>(n+1,vector<int>(3,INT_MIN/2)));// 初始化起点(0,0)对应的dp[1][1]dp[1][1][0]=coins[0][0];// 不使用感化，直接拿起点金币for(intk=1;k<=2;k++){// 使用1次或2次感化，起点收益为max(金币值, 0)（负数不扣钱）dp[1][1][k]=max(coins[0][0],0);}// 遍历网格所有单元格for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(i==1&&j==1)continue;// 起点已初始化，跳过// 处理k=0的情况：从未使用过感化dp[i][j][0]=max(dp[i-1][j][0],dp[i][j-1][0])+coins[i-1][j-1];// 处理k=1和k=2的情况：使用过1次或2次感化for(intk=1;k<=2;++k){// 两种选择取最大值：不使用当前感化 / 对当前单元格使用感化dp[i][j][k]=max(max(dp[i-1][j][k],dp[i][j-1][k])+coins[i-1][j-1],max(dp[i-1][j][k-1],dp[i][j-1][k-1]));}}}// 返回最多使用2次感化的最大收益returndp[m][n][2];}};

复杂度分析

时间复杂度：O(m*n)。m和n为网格的行列数，感化次数k的最大值为2（固定常数），因此总循环次数为m*n*3，时间复杂度为线性级别。
空间复杂度：O(m*n)。三维DP数组的总大小为(m+1)*(n+1)*3，k为常数，因此空间复杂度为O(m*n)。
补充优化：由于每个状态仅依赖上一行和当前行的左侧状态，可将空间进一步优化为O(n)（二维滚动数组）。

力扣 215. 数组中的第K个最大元素

题目描述

力扣 215. 数组中的第K个最大元素

示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：
1 <= k <= nums.length <= 10⁵
-10⁴<= nums[i] <= 10⁴

思路简介

本题是经典的TopK问题，题目要求实现时间复杂度为O(n)的算法，因此最优解为快速选择算法（基于三指针快排的分治剪枝优化）。

核心思路
快速选择算法的核心是「分治+剪枝」：

基于三指针快排的逻辑，随机选择一个基准值，将数组划分为三个区间：小于基准值、等于基准值、大于基准值。
无需对整个数组排序，只需根据三个区间的长度，判断第K大的元素落在哪个区间，仅对目标区间递归处理，舍弃无关区间的计算，从而将平均时间复杂度从快排的O(nlogn)优化到O(n)。

我们要找的是「第K个最大元素」，等价于数组升序排序后「第nums.size() - k + 1个最小元素」。本文代码基于「找第K小元素」的逻辑实现，因此在调用递归函数时，会先对k值做上述转换。

如果快排和解决Topk问题有遗忘的朋友可以看下我这两个博客，其中讲解非常详细，并由完整的手绘图片说明看不懂你打我！

快排+优化：C++ 分治快速排序优化三指针快排力扣 912. 排序数组题解每日一题

TopK的几种解决方法，堆排，快排：C++ 分治快速选择算法堆排序 TopK问题力扣 215. 数组中的第K个最大元素题解每日一题

代码实现

#include<vector>#include<cstdlib>#include<ctime>usingnamespacestd;classSolution{public:// 递归函数：在nums的[begin, end]闭区间内，找第k个最小的元素intTopK(vector<int>&nums,intbegin,intend,intk){// 递归终止条件：区间只有一个元素，该元素就是目标if(begin==end)returnnums[begin];// 1. 随机选择基准值，避免有序数组下的最坏时间复杂度intmark=nums[(rand()%(end-begin+1))+begin];// 三指针定义：intleft=begin-1;// 左区间（<mark）的右边界intright=end+1;// 右区间（>mark）的左边界inti=begin;// 遍历指针// 2. 三指针分区，将数组划分为 <mark、=mark、>mark 三个区间while(i<right){if(nums[i]<mark){// 元素归入左区间，左边界右移，交换元素，遍历指针后移left++;swap(nums[left],nums[i]);i++;}elseif(nums[i]==mark){// 元素归入中间区间，直接后移遍历指针i++;}else{// 元素归入右区间，右边界左移，交换元素，遍历指针不动（交换来的元素未处理）right--;swap(nums[right],nums[i]);}}// 3. 计算三个区间的长度，判断目标元素所在区间intlessLen=left-begin+1;// 左区间长度（小于基准值的元素个数）intequalLen=right-left-1;// 中间区间长度（等于基准值的元素个数）if(k<=lessLen){// 目标在左区间，递归处理左区间returnTopK(nums,begin,left,k);}elseif(k<=lessLen+equalLen){// 目标在中间区间，基准值就是目标元素returnmark;// 原代码返回nums[left+1]，等价于mark，此处更直观}else{// 目标在右区间，调整k值后递归处理右区间returnTopK(nums,right,end,k-lessLen-equalLen);}}intfindKthLargest(vector<int>&nums,intk){// 初始化随机数种子，确保每次运行基准值随机srand(time(nullptr));// 第k大元素 = 升序数组中第 (nums.size() - k + 1) 小的元素returnTopK(nums,0,nums.size()-1,nums.size()-k+1);}};

复杂度分析

时间复杂度：平均O(n)，最坏O(n²)。
快速选择每次仅递归处理一个子区间，平均情况下子区间长度每次减半，总操作次数为n + n/2 + n/4 + ... + 1 ≈ 2n，因此平均时间复杂度为O(n)；最坏情况为每次分区仅排除一个元素，时间复杂度退化为O(n²)，但随机基准值可将最坏情况的出现概率降至极低。
空间复杂度：平均O(logn)，最坏O(n)。
空间消耗主要来自递归栈，平均情况下递归深度为O(logn)，最坏情况下为O(n)。

踩坑记录

三维DP数组的初始化与溢出问题
3418题中，DP数组初始值必须设为INT_MIN/2而非INT_MIN。因为路径的金币可能为负数，若直接用INT_MIN，后续状态转移时加上负数会导致整型溢出，触发未定义行为。同时，开m+1、n+1的数组维度，能有效规避第一行、第一列的边界判断，减少初始化的复杂度。
DP状态定义的一致性
3418题的DP数组存在「数组下标与网格坐标的错位」，写状态转移时必须严格保持dp[i][j]对应coins[i-1][j-1]，否则会出现数组越界或逻辑错误。
TopK问题的第k大/第k小转换
215题中，第k大和第k小的转换极易出错，必须明确：长度为n的数组中，第k大元素 = 升序排序后第n-k+1小的元素，转换时k值计算错误会直接导致结果错误，还有要注意在递归过程中K由于舍弃部分数组导致的变化。
快速选择的随机基准值
面试中实现快速选择时，必须添加随机基准值的逻辑。若使用固定基准（如区间第一个元素），在有序数组的测试用例中会直接退化为O(n²)的时间复杂度，不仅会超时，也会影响面试官的评价。
三指针分区的指针移动逻辑
215题的三指针分区中，元素归入右区间时，遍历指针i不能后移——因为交换过来的元素还未经过判断，需要重新处理，否则会出现分区错误、元素遗漏的问题。