【算法/训练】：贪心（算法理论学习及实践）

IsLand1314

发布于 2025-06-02 11:57:33

6930

文章被收录于专栏：学习之路学习之路

📃个人主页：island1314

前言 🚀

基本概念

🔥 贪心算法（greedy algorithm，又称贪婪算法），在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪心算法关键是：贪心策略的选择

特性

贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质

1. 贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
证明的大致过程为：
- 首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。
- 做了贪心选择后，原问题简化为规模更小的类似子问题。
- 然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。
- 其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质

2. 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

3. 贪心算法与动态规划算法的差异

动态规划和贪心算法都是一种递推算法，均有最优子结构性质，通过局部最优解来推导全局最优解。
两者之间的区别在于：
- 贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。
- 动态规划算法中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。

贪心算法：使用情况

举个例子： 桌面上有 6 张纸币，面额分别为 100，70，50， 20，20，10，现在我们可以拿走 3 张纸币，要求总金额最大，该怎么拿

我相信大家一看到这个问题，肯定就会想着拿最大的那三张就行了，其实这个想法是没错的，但是我们可以把这个想法分解一下：
我们不考虑拿 3 张，我们只考虑拿走一张的最大值（局部最优），那么这个问题就可以拆解为拿三次的情况，第一次拿 100，第二次拿 70，第三次拿 50，那我们最多可以拿 220

具体例题如下 📚

1. 买卖股票的最好时机(二)

思路：只要当天价格比上一天价格大，就累加，示意图如下，然后算出最大利润即可

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int maxProfit(vector<int>& prices) {
	// write code here
	int ret = 0;
	for (int i = 0; i < prices.size(); i++)
	{
		if (prices[i] > prices[i - 1]) ret += prices[i] - prices[i - 1];
	}
	return ret;
}


int main()
{
	int n;
	cin >> n;
	vector<int> prices;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		prices.emplace_back(x);
	}
	cout << maxProfit(prices) << endl;

	return 0;
}

2. 拼数

解析： 先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之则把a排在b的后面，最后输出排序后的字符串，即可得到最大的整数（如果求最小的整数，则从小到大排序）。 举例说明：a=‘123’，b=‘71’，a+b='12371'，b+a=‘71123’，所以a+b<b+a，将b排在前面 注意：正常的字符串存在比较缺陷，如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，所以A+B > B+A ，而实际上’32132’ < ’32321’。 具体步骤如下： 1.获取n 2.依次获取n个正整数，将整数转换为字符串：声明字符串数组a[n]，将获取到的正整数存入数组a中，即可实现正整数到字符串的转换 3.自定义排序函数：如果a+b>b+a，则把a排在前面，否则将b排在前面（对于字符串a、b，a+b表示连接两个字符串形成一个新串） 4.从大到小输出排序后的字符串即可得到最大的整数

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

bool cmp(string s1, string s2){
	return s1 > s2;
}
int main(){
	int n;
	cin >> n;
	vector<string> s;
	for (int i = 0; i < n; i++){
		string ch;
		cin >> ch;
		s.push_back(ch);
	}
	sort(s.begin(), s.end());

	for (auto e : s) cout << e;
	return 0;
}

3. 组队竞赛

思路：排序+贪心。每次选择当前剩余的人之中，水平最高的两个人和水平最低的一个人组队，这样就能最大化团队水平中位数的值。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;


// ———— 乒乓球筐
void solve1()
{
	string s, t;
	while (cin >> s >> t)
	{
		map<char, int> mp;
		for (auto e : s)
		{
			mp[e]++;
		}
		for (auto e : t)
		{
			mp[e]--;
		}
		int f = 1;
		for (auto e : mp)
		{
			if (e.second < 0) f = 0;
		}
		if (f == 0) cout << "No" << endl;
		else cout << "Yes" << endl;
	}

}

const int N = 300010;
int a[N];
void solve2()
{
	int n;
	cin >> n;
	for (int i = 0; i < 3 * n; i++) {
		cin >> a[i];
	}
	sort(a, a + 3 * n);
	long long ans = 0;
	int r = 3 * n - 1, l = 0;
	while (l < n)
	{
		ans += a[r - 1];
		r -= 2;
		l++;
	}
	cout << ans << "\n";
}


int main()
{
	solve2();
}

4. 拼数

思路： 先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之则把a排在b的后面，最后输出排序后的字符串，即可得到最大的整数（如果求最小的整数，则从小到大排序）。举例说明：a=‘123’，b=‘71’，a+b='12371'，b+a=‘71123’，所以a+b<b+a，将b排在前面注意：正常的字符串存在比较缺陷，如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，所以A+B > B+A ，而实际上’32132’ < ’32321’。具体步骤如下： 1.获取n 2.依次获取n个正整数，将整数转换为字符串：声明字符串数组a[n]，将获取到的正整数存入数组a中，即可实现正整数到字符串的转换 3.自定义排序函数：如果a+b>b+a，则把a排在前面，否则将b排在前面（对于字符串a、b，a+b表示连接两个字符串形成一个新串） 4.从大到小输出排序后的字符串即可得到最大的整数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(string a, string b) {
	return a + b > b + a;
}
int main() {
	int n;
	cin >> n;
	vector<string> ans(n);
	for (int i = 0; i < n; i++) 
		cin >> ans[i];
	sort(ans.begin(), ans.end(), cmp);
	for (auto e : ans) cout << e;
	return 0;
}

5. 华华听月月唱歌

思路：该题的贪心策略就是每次向后寻找能跳到的区间里面右端最远的那一个，如果挑不到或者最后不足N那么就证明无法满足，因此我们可以定义一个cmp函数来进行排序。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct node {
	int l, r; //左右区间
};


bool cmp(node a,node b) {
	if (a.l != b.l) return a.l < b.l;
	return a.r > b.r;
}


int main(){
	int n, m;
	cin >> n >> m;
	vector<node> ans(m);
	for (int i = 0; i < m; i++) 
		cin >> ans[i].l >> ans[i].r;
	
	sort(ans.begin(), ans.end(), cmp);
	if (ans[0].l != 1) {//如果最左边节点不是1的话，就做不到
		cout << -1 << endl;
		return 0;
	}

	int ret = 1; //记录最少选择区间
	int maxr = ans[0].r, tmp = ans[0].r; //记录最大右边
	
	for (int i = 1; i < m && maxr < n;) {
		while (i < m && ans[i].l <= maxr + 1) { //记住是 + 1,因为 [1,3] 和[4, 5]可以直接相连
			tmp = max(tmp, ans[i].r); //记录在当前最大的右边的时候，可以进来多少个左边
			i++;
		}
		if (tmp == maxr) break;
		ret++;
		maxr = tmp;
	} 

	if (maxr >= n) //当最大右边大于等于n时即可
		cout << ret << endl;
	else cout << -1 << endl;

	return 0;
}

6. 非对称之美

思路： 这题我们的主要思路是用贪心，

先判断整个字符串是否是回文，那么就从后面往前走，逐渐-1
还有个特殊情况，字符串中字符全都相同的时候，就直接返回0
易知可输出答案只有0，n，n - 1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve3() {
	string s;
	cin >> s;
	int n = s.size();
	// 1. 判断是否全部相同
	bool f = false;  //判断是否是回文
	for (int i = 1; i < n; i++) {
		if (s[i] != s[0]) {
			f = true;
			break;
		}
	}
	if (f == false){
		cout << 0 << endl;
		return;
	}

	// 2. 不是相同字符
	f = false;
	// 3. 判断本身是否为回文
	int l = 0, r = n - 1;
	while (l < r) {
		if (s[l] == s[r]) l++, r--;
		else {
			f = true; //本身不是回文
			break;
		}
	}
	if (f) cout << n << endl;
	else cout << n - 1 << endl;
}


int main() 
{
	solve3();
	return 0;
}

7. 主持人调度（二）

//方法一：差分数组的映射
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
	map<int, int> mp;
	for (int i = 0; i < startEnd.size(); i++) {
		mp[startEnd[i][0]]++; //左边 ++
		mp[startEnd[i][1]]--; //右边 --
	}
	int ans = 0, res = 0;
	for (auto ip : mp) {
		res += ip.second;
		ans = max(ans, res);
	}
	return ans;
}

//方法二：小根堆，只进入右端点，进入点的左端点和堆顶作比较
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
	sort(startEnd.begin(), startEnd.end(), [&](vector<int> a, vector<int>b)->bool
		{
			return a[0] < b[0];
		});
	priority_queue<int,vector<int>,greater<int>> heap;
	heap.push(startEnd[0][1]);//入右端点
	
	for (int i = 1; i < n; i++) {
		int a = startEnd[i][0], b = startEnd[i][1];
		if (a >= heap.top()) //无重叠
		{
			heap.pop();
			heap.push(b);
		}
		else heap.push(b); //有重叠
	}
	return heap.size();
}

8. 活动安排

思路：

先进行排序，然后如果两个活动出现了交集，就选择右端点较小的那个活动。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;

struct node{
	int a, b;
}arr[N];

bool cmp(node a, node b)
{
	return a.b < b.b;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> arr[i].a >> arr[i].b;
	sort(arr, arr + n, cmp);
	int ret = 1;
	int premin = arr[0].b;
	for (int i = 0; i < n; i++)
	{
		if (arr[i].a >= premin) {
			ret++;
			premin = arr[i].b;
		}
	}
	cout << ret << endl;

	return 0;
}

9. 最大差值

思路：

记录前 i 个数的最小数，用当前数减去最小数，然后用一个数字记录最大差值即可

int getDis(vector<int>& A, int n) {
    int mini = 1e5 + 10, maxi = 0;
    for (int i = 0; i < n; i++)
    {
        mini = min(A[i], mini);
        maxi = max(A[i] - mini, maxi);
    }
    return maxi;
}

10. 栈和排序

思路：栈 + 贪心

优先让当前最大数先出栈
依次进栈
先更新目标值
出栈

class Solution {
public:
    bool h[500005];
    vector<int> solve(vector<int>& a) {
        int n = a.size();
        stack<int> st;
        vector<int> ret;
        int aim = n;
        for (auto x :a)
        {
            st.push(x);
            h[x] = true;
            // 更新目标值
            while (h[aim]) {
                aim--;
            }
            while (st.size() && st.top() >= aim){
                ret.push_back(st.top());
                st.pop();
            }
        }
        return ret;
    }
};

11. 区间问题

1, 合并区间

题目链接：56. 合并区间

贪心策略:

先按照区间的「左端点」排序:此时我们会发现，能够合并的区间都是连续的，b.然后从左往后，按照求「并集」的方式，合并区间。

如何求并集: 由于区间已经按照「左端点」排过序了，因此当两个区间「合并」的时候，合并后的区间：

左端点就是「前一个区间」的左端点;
右端点就是两者「右端点的最大值」。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
    {
        sort(intervals.begin(), intervals.end());
        int l = intervals[0][0], r = intervals[0][1];
        vector<vector<int>> ret;
        for(int i = 1; i < intervals.size(); i++)
        {
            int a = intervals[i][0], b = intervals[i][1];
            if(r >= a){
                r = max(r, b);
            }
            else{
                ret.push_back({l, r});
                l = a;
                r = b;
            }
        }
        ret.push_back({l, r});
        return ret;
    }
};

2, 非重叠区间

题目链接：435. 无重叠区间

贪心策略:

按照「左端点」排序;
当两个区间「重叠」的时候，为了能够「在移除某个区间后，保留更多的区间」，我们应该把「区间范围较大」的区间移除。

如何移除区间范围较大的区间

由于已经按照「左端点」排序了，因此两个区间重叠的时候，我们应该移除「右端点较大」的区间

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int ret = 0, l = intervals[0][0], r = intervals[0][1];
        for(int i = 1; i < intervals.size(); i++)
        {
            int a = intervals[i][0], b = intervals[i][1];
            if(a < r){
                ret++;
                r = min(r, b);
            }
            else {
                r = b;
            }
        }
        return ret;
    }
};

3, 重叠区间数量

题目链接：452. 用最少数量的箭引爆气球

贪心策略:

按照左端点排序，我们发现，排序后有这样一个性质:「互相重叠的区间都是连续的」;
这样，我们在射箭的时候，要发挥每一支箭「最大的作用」，应该把「互相重叠的区间」统一引爆。

如何求互相重叠区间?

由于我们是按照「左端点」排序的，因此对于两个区间，我们求的是它们的「交集」:

左端点为两个区间左端点的「最大值」(但是左端点不会影响我们的合并结果，所以可以忽略)
右端点为两个区间右端点的「最小值」。

class Solution {
public:
    // 相当于求重合区间数量
    int findMinArrowShots(vector<vector<int>>& points) {
        // 1. 排序
        sort(points.begin(), points.end());
        // 2. 求互相重叠数量
        int ret = 1, r = points[0][1]; // 初始数量为 1
        for(int i = 1; i < points.size(); i++)
        {
            int a = points[i][0], b = points[i][1];
            if(a <= r){
                r = min(r, b);
            }
            else {
                ret++;
                r = b;
            }
        }
        return ret;
    }
};

4, 区间套娃

题目链接：354. 俄罗斯套娃信封问题

思路：重写排序 + 贪心 + 二分

当我们把整个信封按照「下面的规则」排序之后:

左端点不同的时候:按照「左端点从小到大」排序;
左端点相同的时候:按照「右端点从大到小」排序

我们发现，问题就变成了仅考虑信封的「右端点」，完完全全的变成的「最长上升子序列」的模型。那么我们就可以用「贪心+二分」优化我们的算法。

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [&](const auto& a, const auto& b){
            return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
        });
        // 贪心 + 二分
        vector<int> ret;
        ret.push_back(envelopes[0][1]);
        for(int i = 1; i < envelopes.size(); i++)
        {
            int b = envelopes[i][1];
            if(b > ret.back()){
                ret.push_back(b);
            }
            else{
                int l = 0, r = ret.size() - 1;
                while(l < r)
                {
                    int mid = (l + r) / 2;
                    if(ret[mid] < b ) l = mid + 1;
                    else r = mid;
                }
                ret[l] = b;
            }
        }
        return ret.size();
    }
};

12. 整数问题

1, 坏了的计算器

题目链接：991. 坏了的计算器

贪心策略：【正难则反】

当「反着」来思考的时候，我们发现

当 end<= begin 的时候，只能执行「加法」操作;
当 end > begin 的时候，对于「奇数」来说，只能执行「加法」操作;对于「偶数」来说，最好的方式就是执行「除法」操作

这样的话，每次的操作都是「固定唯一」的。

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        // 正难则反
        int ret = 0;
        while(target > startValue)
        {
            if(target % 2 == 1) target += 1;
            else {
                target /= 2;
            }
            ret++;
        }
        return ret + startValue - target;
    }
};

2, 整数替换

题目链接：397. 整数替换

贪心策略: 我们的任何选择，应该让这个数尽可能快的变成1

对于偶数：只能执行除 2操作，没有什么分析的;

对于奇数：

当 n == 1 的时候，不用执行任何操作;
当 n == 3 的时候，变成 1 的最优操作数是 2;
当 n > 1 && n%4 == 1 的时候，那么它的二进制表示是......01，最优的方式应该选择 -1，这样就可以把末尾的1干掉，接下来执行除法操作，能够更快的变成
当 n > 3 && n%4 == 3 的时候，那么它的二进制表示是......11，此时最优的策略应该是 +1，这样可以把一堆连续的1转换成 0，更快的变成 1。

class Solution {
public:
    int integerReplacement(int n) {
        int ret = 0;
        while(n > 1)
        {
            if(n % 2 == 0){
                n /= 2;
            }
            else{
                if(n == 3){
                    n -= 1;
                }
                else if(n % 4 == 1){
                    n -= 1;
                }
                else if(n % 4 == 3){
                    n = n / 2 + 1;
                    ret++;
                }
            }
            ret++;
        }
        return ret;
    }
};

3, 可被三整除的最大和

题目链接：1262. 可被三整除的最大和

思路：正难则反 + 贪心 + 分类讨论

正难则反:

我们可以先把所有的数累加在一起，然后根据累加和的结果，贪心的删除一些数。

分类讨论:

设累加和为 sum，用 x 标记 %3 == 1 的数，用 y 标记 %3 == 2 的数。

那么根据 sum 的余数，可以分为下面三种情况:

sum %3 == 0，此时所有元素的和就是满足要求的，那么我们一个也不用删除;，
sum %3 == 1，此时数组中要么存在一个 x，要么存在两个 y。因为我们要的是最大值，所以应该选择 x 中最小的那么数，记为x1，或者是y 中最小以及次小的两个数，记为 y1，y2。
1. 那么，我们应该选择两种情况下的最大值：max(sum-x1，sum - y1 -y2）；
sum %3 == 2，此时数组中要么存在一个 y，要么存在两个 x。因为我们要的是最大值，所以应该选择 y 中最小的那么数，记为y1，或者是x 中最小以及次小的两个数，记为 x1，x2。
1. 那么，我们应该选择两种情况下的最大值：max(sum-y1，sum - x1 -x2）；

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        const int INF = 0x3f3f3f3f; 
        int sum = 0;
        // x1 < x2, y1 < y2
        int x1 = INF, x2 = INF, y1 = INF, y2 = INF;
        for(auto &num: nums)
        {
            sum += num;
            if(num % 3 == 1){
                if(num < x1) x2 = x1, x1 = num;
                else if(num < x2) x2 = num; 
            }
            else if(num % 3 == 2){
                if(num < y1) y2 = y1, y1 = num;
                else if(num < y2) y2 = num; 
            }
        }
        if(sum % 3 == 0) return sum;
        else if(sum % 3 == 1) return sum - min(x1, y1 + y2);
        else return sum - min(y1, x1 + x2);
    }
};

4, 单调递增的数字

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

解法(贪心)

为了方便处理数中的每一位数字，可以先讲整数转换成字符串
从左往右扫描，找到第一个递减的位置
从这个位置向前推，推到相同区域的最左端
该点的值 -1，后面的所有数统一变成 9

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 stoi(s); // 直接返回
        // 回推找到不等的位置
        while(i - 1 >= 0 && s[i] == s[i - 1]) i--;
        s[i]--;
        
        i++;
        while(i < m) s[i++] = '9';
        return stoi(s);
    }
};

13. 排列问题

1. 排列数字使相邻数字不等

题目链接：1054. 距离相等的条形码

贪心策略:

每次处理一批相同的数字，往n个空里面摆放;
每次摆放的时候，隔一个格子摆放一个数;
优先处理出现次数最多的那个数

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        // 1. 哈希统计, 并且找出出现最多次数的数字
        unordered_map<int, int> hash;
        int maxVal, maxCnt = 0; 
        for(auto &x: barcodes) {
            if(maxCnt < ++hash[x]){
                maxVal = x;
                maxCnt = hash[x];
            }
        }
        // 2. 处理出现最多次数的数字
        int n = barcodes.size(), ind = 0;
        vector<int> ret(n);
        while(maxCnt--){
            ret[ind] = maxVal;
            ind += 2;
        }
        // 3. 处理剩下的数
        hash.erase(maxVal);
        for(auto &[x, y]: hash){
            while(y--){
                if(ind >= n) ind = 1;
                ret[ind] = x;
                ind += 2;
            }
        }
        return ret;
    }
};

2. 排列字符串使相邻字符不等

题目链接：767. 重构字符串

class Solution {
public:
    string reorganizeString(string s) {
        int hash[26] = {0};
        char maxVal;
        int maxCnt = 0;
        // 1. 找出最多
        for(auto &ch: s){
            if(maxCnt < ++hash[ch - 'a']){
                maxVal = ch;
                maxCnt = hash[ch - 'a'];
            }
        }
        // 2. 判断是否存在
        int n = s.size();
        if(maxCnt > (n + 1) / 2) return "";
        // 3. 处理最多
        int ind = 0;
// C++中的一种字符串初始化方式，表示创建一个长度为n、所有字符均为空格（' '）的字符串对象。
        string ret(n, ' '); // 新方法
        while(maxCnt--){
            ret[ind] = maxVal;
            ind += 2;
        }
        hash[maxVal - 'a'] = 0; // 记得除掉出现次数最多的字符
        // 4. 处理其他
        for(int i = 0; i < 26; i++)
        {
            while(hash[i]--){
                if(ind >= n) ind = 1;
                ret[ind] = i + 'a';
                ind += 2;
            }
        }
        return ret;
    }
};

14. 行驶问题

1. 加油站

题目链接：134. 加油站

暴力解法:

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

贪心优化:

我们发现，当从 i位置出发，走了 step 步之后，如果失败了。那么[i，i+ step]这个区间内任意一个位置作为起点，都不可能环绕一圈。
因此我们枚举的下一个起点，应该是 i + step + 1

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, step = 0;
            for(; step < n; step++)
            {
                int pos = (i + step) % n;
                rest += gas[pos] - cost[pos];
                if(rest < 0) break;
            }
            if(rest >= 0) return i;
            i = i + step;
        }
        return -1;
    }
};

15. 序列问题

1. 递增的三元子序列

题目链接：334. 递增的三元子序列

贪心策略:

最长递增子序列的简化版。
不用一个数组存数据，仅需两个变量即可。也不用二分插入位置，仅需两次比较就可以找到插入位置

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int a = nums[0], b = INT_MAX;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] > b) return true;
            else if(nums[i] > a) b = nums[i];
            else a = nums[i];
        }
        return false;
    }
};

2. 最长递增子序列

题目链接：300. 最长递增子序列

贪心策略:

在考虑最长递增子序列的长度的时候，其实并不关心这个序列长什么样子，我们只是关心最后一个元素是谁。
这样新来一个元素之后，我们就可以判断是否可以拼接到它的后面。
因此，我们可以创建一个数组，统计长度为 x的递增子序列中，最后一个元素是谁。
为了尽可能的让这个序列更长，我们仅需统计长度为 x的所有递增序列中最后一个元素的「最小值」。
统计的过程中发现，数组中的数呈现「递增」趋势，因此可以使用「二分」来查找插入位置。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);

        for(int i = 1; i < n; i++)
        {
            // 看是否能放在最后一个位置
            if(nums[i] > ret.back()) ret.push_back(nums[i]); 
            else{
                int l = 0, r= ret.size() - 1;
                while(l < r){
                    int mid = (r + l) >> 1;
                    if(ret[mid] < nums[i]) l = mid + 1;
                    else r = mid;
                }
                ret[l] = nums[i];
            }
        }

        return ret.size();
    }

};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串