【贪心算法】贪心算法五

Ne0inhk

23 Mar 2026 — 18 min read

贪心算法五

1.跳跃游戏 II
2.跳跃游戏
3.加油站
3.单调递增的数字

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.跳跃游戏 II

题目链接：45. 跳跃游戏 II

题目分析：

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处。这句话特别重要的地方就是任意。

下面举个例子，刚开始在0号位置最大跳跃长度是3，可以跳到下标3的位置。

你可以跳转到任意 nums[i + j] 处，这句话意思，nums[i]里面存的3是最大跳跃长度，你可以选择跳3步、跳2步、跳1步。

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

算法原理：

贪心(X)

刚开始处于0好位置，这里有一个最大跳跃长度，那每次跳跃的时候就非常贪心的跳最长跳跃长度。但是这种贪心是错的。

2. 动态规划

这个模型无非就是从左往右的一个模型，其实就是动规里面非常常规的线性dp问题。

1.状态表示

dp[i] 表示：从 0 位置开始，到达 i 位置的时候最小跳跃次数

2.状态转移方程

根据最近一步划分情况：

能够到 i 位置的前提是要满足 nums[j] + j >= i，说明能够从 j 位置到达 i 位置，那到达 j 位置的最小跳跃次数在加上从 j 到 i 这一跳跃次，就是到达 i 位置最小跳跃次数，j的位置有很多，因此外面要求dp[i]的最小值。

3.初始化

dp[0] = 0 初始就在0位置，然后要取dp[i]的最小值，因此0位置之后可以初始化 INT_MAX

4.填表顺序

从左往右

5.返回值

dp[i] 表示：从 0 位置开始，到达 i 位置的时候最小跳跃次数，我们要的是到底n-1位置的最小跳跃次数，因此返回dp[n-1]

classSolution{public:intjump(vector<int>& nums){// 动态规划int n = nums.size(); vector<int>dp(n, INT_MAX); dp[0]=0;for(int i =1; i < n;++i)for(int j =0; j < i;++j)if(nums[j]+ j >= i) dp[i]=min(dp[i], dp[j]+1);return dp[n -1];}};

虽然可以通过，但是实际复杂度是O(N^2)

类似于层序遍历的过程

刚开始在2这个位置，此时起跳可以跳到3和1的位置。2这里可以表示第1次起跳的位置，3和1表示第2次起跳的位置。

通过第2次起跳的位置，我们可以得到第3从起跳的位置，然后把重叠的删除，这里其实也有一点小贪心，如果能从第2次的1起跳，那为什么还要从第3次重叠的1起跳呢？跳跃次数更多了。所以只有1和4是第三次起跳的位置。

同理从第3次起跳位置，我们可以得到第4次起跳位置，

你会发现这里类似于层序遍历，每次都能知道起跳的左端点和右端点，然后遍历这一层的时候，又能找到下一层的左端点和右端点。只要发现更新出来下一次起跳位置能够覆盖到n-1位置的时候就停止，因为次数已经可以跳到最后一个位置了

如何实现呢？
我们仅需搞两个指针，left指向当前起跳的左端点，right指向当前起跳的右端点，把这个区间遍历一遍就可以找到下一个起跳区间，其中找左端点很好找就是right + 1，找右端点就是在遍历的过程中，拿着nums[i] + i 找到其中的最大值就是右端点。

在这个遍历过程中，我们仅需遍历一次就行了，所以时间复杂度是O(N)

classSolution{public:intjump(vector<int>& nums){int left =0, right =0, maxPos =0, ret =0, n = nums.size();while(left <= right)// 保险的写法，以防跳不到 n - 1 的位置{if(maxPos >= n -1)// 先判断⼀下是否已经能跳到最后⼀个位置{return ret;}// 遍历当成层，更新下⼀层的最右端点 for(int i = left; i <= right;++i){ maxPos =max(maxPos, nums[i]+ i);} left = right +1; right = maxPos;++ret;}return-1;// 跳不到的情况}};

2.跳跃游戏

题目链接：55. 跳跃游戏

题目分析：

这道题和上面几乎一模一样，无非上面问的是跳到最后一个位置最小跳跃次数，这道题问的是能否跳到最后一个位置。

算法原理：

完全参考上面的解法3：利用层序遍历的过程

classSolution{public:boolcanJump(vector<int>& nums){int left =0, right =0, maxPos =0, n = nums.size();while(left <= right){if(maxPos >= n -1){returntrue;}for(int i = left; i <= right;++i){ maxPos =max(maxPos, nums[i]+ i);} left = right +1; right = maxPos;}returnfalse;}};

3.加油站

题目链接：134. 加油站

题目分析：

选择某个加油站为出发点，环绕一周看是否能回到出发点。如果可以就返回对应的下标，不能就返回-1。

初始时油箱是空的，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i]，油箱容量是无限的。

假设从3位置出发，刚开始油箱为空，此时可以补充1升汽油，但是需要3升汽油才能到下一个位置。所以这个位置不可以，同理4和5都不可以。

可以从1位置出发，从这里可以补充4升汽油，仅需消耗1升就可以到下一个位置，到下一个位置还剩下3升

到2的位置，补充5升，现在共有8升，消耗2升，到下一个位置还有6升

然后补充1升，消耗3升，到下一个位置还剩4，在补充2升，消耗4升，到下一个位置还剩2升，在补充3升，消耗5升，到出发点正好剩下0，可以到达，返回3。

算法原理：

解法一：暴力解法 -> 枚举

首先可以想到一个优化，仅需考虑g和c的差就可以了，比如第一个位置会加1升油，消耗3升油，它们的差就是从这个加油站获得的净收益。如果从负开始走绝对是走不到下一个位置的，所以肯定会选择净收益为正的作为出发点。

我们这道题其实特别像是一道模拟的题，任意枚举一个位置看看从这个位置能不能绕一圈会回来就可以。如果不能就去枚举下一个位置。

所以我们的暴力策略就很简单：

依次枚举所有的起点
从起点开始，模拟一遍加油的流程即可

虽然策略很简单，但是要注意这里是有环的，所以写代码的时候要考虑如何从最后一个位置回到0位置。

我们的贪心就是根据暴力优化来的，所以先搞定暴力的代码。然后优化的时候仅需加一句代码，就能将时间复杂度从O(N^2)变成O(N)

如何实现暴力的代码？

这里我们主要考虑就是如何从最后一个位置回到第一个位置，其实这里两层for循环就可以搞定，我们创建一个变量step，用这个变量表示从 i 往后走了多少步，step变化是从 0 ~ n - 1。然后（i + step）% n (数组大小) 就可以从最后一个位置回到第一个位置。

classSolution{public:intcanCompleteCircuit(vector<int>& gas, vector<int>& cost){int n = gas.size();for(int i =0; i < n;++i)// 依次枚举所有的起点{int rest =0;// 标记一下净收益int step =0;for(; step < n;++step)// 枚举往后走的步数{int index =(i + step)% n;// 求出走 step 步之后的下标 rest = rest + gas[index]- cost[index];if(rest <0)break;}if(rest >=0)return i;}return-1;}};

解法二：优化 -> 找规律（贪心）

diff表示g-c的差，我们的暴力解法是依次固定一个位置为起点，从这个起点开始模拟加油流程，其实就是把净收益加一下。

如果发现从a加到f小于0了，说明从f这个位置开始就不能往后走了，所以从a为起来最多能到f这个位置。这里有一个等式。

我们的暴力是枚举下一个起点然后在走。然后我们这里也有个不等式，

我们要想从a走到b，一定是a>=0的，从a加到f < 0，现在第二个不等式又少了a，那更是< 0

同理从c为起点也是越不过f的，a + b >= 0才能到c，等式少了a+b，那更小于0

所以说发现有一个起点点都跑不到某个位置，那中间的都不用在考虑了，不用在枚举了。直接让 i 指针更新到五角星后面的一个位置，也就是 i = i + step + 1

我们最差会遍历数组两遍，假设还是以a为起点，发现到h走不到了，下一个位置就是i，最差我们绕回去在遍历一遍再走到h位置，相当于遍历了数组两遍，然后接下来更新 i 的时候是 i + step + 1 此时就已经越界了。所以最差遍历数组两遍，时间复杂度O(N)

classSolution{public:intcanCompleteCircuit(vector<int>& gas, vector<int>& cost){int n = gas.size();for(int i =0; i < n;++i)// 依次枚举所有的起点{int rest =0;// 标记一下净收益int step =0;for(; step < n;++step)// 枚举往后走的步数{int index =(i + step)% n;// 求出走 step 步之后的下标 rest = rest + gas[index]- cost[index];if(rest <0)break;}if(rest >=0)return i; i = i + step;//优化}return-1;}};

3.单调递增的数字

题目链接：738. 单调递增的数字

题目分析：

算法原理：

解法一：暴力解法 -> 暴力枚举

不是给了我们一个n，然后让找到小于等于n的最大数字，且数字是单调递增的。
所以我们可以从n枚举到0，只要找到数字是单调递增的，就返回。因为我们是从大到小枚举所以这个数一定是小于等于n并且是最大的那个数。

从大到小的顺序，枚举 [n，0] 区间内的数字
判断数字是否是 “单调递增的”

这里最主要的就是判断一个数是单调递增的。肉眼很好判断，但是让计算机不好判断，这里我们有两个常用方法：

第一种方法：我们遇到有个数字的时候，如果想处理某一位的时候，最常用的方式就是将数字转化为字符串。

比如要找数字中的每一位，如果单看数字1234你很难找每一位，但是我们可以将1234 转化为 “1234”，此时就可以用指针来遍历每一位

classSolution{public:intmonotoneIncreasingDigits(int n){for(int i = n; i >=0;--i){ string nums =to_string(i);int j =0, m = nums.size();for(; j < m -1;++j){if(nums[j]> nums[j +1])break;}if(j == m -1)return i;}return-1;}};

第二种方法：% 10 ， / 10

prev记录之前%10得到的数字，cur记录/10之后然后当前%10得到的数字。

classSolution{public:intmonotoneIncreasingDigits(int n){for(int i = n; i >=0;--i){int prev = INT_MAX, cur =0, num = i;while(num){ cur = num %10;if(cur > prev)break; prev = cur; num /=10;}if(num ==0)return i;}return-1;}};

这两种方法都会超时！时间复杂度是O(nlogn)，O(logn)表示把数字中的每一位都提取出来时间复杂度是O(logn)

解法二：贪心（找规律）

假设有下面这样一个数，我们观察1-5是递增的，从5后面开始就是递减的。此时第一个贪心，如果前面的数是递增的我们会不会去修改它？肯定不会！修改高位势必会给高位某个数减小，影响太大了。

如果高位单调递增的话，我们不去修改

从5之后开始下降，我们最终要想找一个单调递增的话，调整一下后面的数使它从5开始递增并且尽可能的大，但是这个想法是实现不了的，你是会让4变成5，但是整个数相比之前就变大了。所以这个策略不行，调整4367使它从5之后开始递增是实现不了的。原因就是后面数的变化受到5的限制。如何解除这个限制呢？让这个5减小1变成4，然后的数都变成9，绝对是最大递增的。

从左往右，找到第一个递减的位置，使其减小1，后面的数全部修改成 9

但是这里还有个问题，比如下面这个数，5是重复的，从左到右扫描到最后一个5的位置，但是执行刚才的策略是让最后一个5减少1，后面数都变成9，但是不行啊，你让最后一个5变成4，这个数就不是一个递增的了。其实我们应该调整第一个5变成4，后面的数都变成9

从左往右，找到第一个递减的位置，从这个位置向前推，推到相同区域的最左段使其减小1，后面的数全部修改成 9

classSolution{public:intmonotoneIncreasingDigits(int n){ string s =to_string(n);// 把数字转化成字符串int i =0, m = s.size();// 找第⼀个递减的位置while(i +1< m && s[i]<= s[i +1])++i;if(i +1== m)return n;// 判断⼀下特殊情况// 回推while(i -1>=0&& s[i]== s[i -1])--i; s[i]--;for(int j = i +1; j < m;++j) s[j]='9';returnstoi(s);}};

证明：

证明方法：反证法

假设贪心解是错误的，那必定会存在一个最优解，证明一下这个最优解是不存在的，那我们的贪心解就是最优的。