【贪心算法】（第十篇）
目录
加油站（medium）
题目解析
讲解算法原理
编写代码
单调递增的数字（medium）
题目解析
讲解算法原理
编写代码
加油站（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
在⼀条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有⼀辆油箱容量⽆限的的汽⻋，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油
cost[i] 升。你从其中的⼀个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路⾏驶⼀周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯⼀的。
⽰例1:
输⼊:gas=[1,2,3,4,5],cost=[3,4,5,1,2]
输出:3
解释:
从3号加油站(索引为3处)出发，可获得4升汽油。此时油箱有=0+4=4升汽油开往4号加油站，此时油箱有4-1+5=8升汽油
开往0号加油站，此时油箱有8-2+1=7升汽油
开往1号加油站，此时油箱有7-3+2=6升汽油
开往2号加油站，此时油箱有6-4+3=5升汽油
开往3号加油站，你需要消耗5升汽油，正好⾜够你返回到3号加油站。因此，3可为起始索引。
⽰例2:
输⼊:gas=[2,3,4],cost=[3,4,3]
输出:-1
解释:
你不能从0号或1号加油站出发，因为没有⾜够的汽油可以让你⾏驶到下⼀个加油站。我们从2号加油站出发，可以获得4升汽油。此时油箱有=0+4=4升汽油
开往0号加油站，此时油箱有4-3+2=3升汽油
开往1号加油站，此时油箱有3-3+3=3升汽油
你⽆法返回2号加油站，因为返程需要消耗4升汽油，但是你的油箱只有3升汽油。因此，⽆论怎样，你都不可能绕环路⾏驶⼀周。
提⽰:
◦ gas.length == n
◦ cost.length == n
◦ 1 <= n <= 10(5)
◦ 0 <= gas[i], cost[i] <= 10(4)
讲解算法原理
解法（暴⼒解法->贪⼼）：
暴⼒解法：
a. 依次枚举所有的起点；
b. 从起点开始，模拟⼀遍加油的流程
贪⼼优化：
我们发现，当从 i 位置出发，⾛了 step 步之后，如果失败了。那么 [i, i + step] 这个区间内任意⼀个位置作为起点，都不可能环绕⼀圈。
因此我们枚举的下⼀个起点，应该是 i + step + 1 。
编写代码
c++算法代码：
class Solution
{
public:
int canCompleteCircuit(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;
}
};java算法代码：
class Solution
{
public int canCompleteCircuit(int[] gas, int[] cost)
{
int n = gas.length;
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;
}
}单调递增的数字（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
当且仅当每个相邻位数上的数字x和y满⾜x<=y时，我们称这个整数是单调递增的。给定⼀个整数n，返回⼩于或等于n的最⼤数字，且数字呈单调递增。
• ⽰例1:
输⼊:n=10
输出:9
• ⽰例2:
输⼊:n=1234
输出:1234
• ⽰例3:
输⼊:n=332
输出:299
• 提⽰:
0<=n<=10^9
讲解算法原理
解法（贪⼼）：
a. 为了⽅便处理数中的每⼀位数字，可以先讲整数转换成字符串；b. 从左往右扫描，找到第⼀个递减的位置；
c. 从这个位置向前推，推到相同区域的最左端；d. 该点的值 -1 ，后⾯的所有数统⼀变成 9 。
编写代码
c++算法代码：
class Solution
{
public:
int monotoneIncreasingDigits(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';
return stoi(s);
}
};java算法代码：
class Solution
{
public int monotoneIncreasingDigits(int n)
{
// 把数字转化成字符串
char[] s = Integer.toString(n).toCharArray();
int i = 0, m = s.length;
// 找第⼀个递减的位置
while(i + 1 < m && s[i] <= s[i + 1]) i++;
if(i == m - 1) 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';
return Integer.parseInt(new String(s));
}
}