算法1：贪心思想

你的名字 2023-03-01 14:56 11阅读 0赞

## 贪心算法，求解最优解， ##

它在每一步都作出当时看起来是最优的选择，通过局部最优从而来选择全局最优，当然这是一种大概率的推测，**不能绝对的认为局部最优一定是全局最优。**

## **实例：** Leetcode122 股票买卖问题：给定一个股票价格数组，求买卖最大利润。(不限交易次数) ##

**思想：** 该算法仅可以用于计算，但计算的过程并不是真正交易的过程，但可以用贪心算法计算题目要求的最大利润。下面说明这个等价性：以 \[1, 2, 3, 4\] 为例，这 4 天的股价依次上升，按照贪心算法，得到的最大利润是：

res =  (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])
    等价于 =>  prices[3] - prices[0]

贪心算法代码：

int MaxProfie(vector<int> &arr)
    {
        
    	int res = 0;
    	for(int  i = 0; i < arr.size() - 1; i ++)
    	{
        
    		int profie = arr[i + 1] - arr[i];
    		if(profie > 0)
    		{
        
    			res += profie;
    		}
    	}
    	return res;
    }

**实例：** Leetcode 435 无重叠区间问题：给定含有不同区间的数组，输出删除几个区间保证不重叠。  
输入: \[ \[1,2\], \[2,3\], \[3,4\], \[1,3\] \]  
输出: 1  
解释: 移除 \[1,3\] 后，剩下的区间没有重叠。

bool cmpare(const vector<int> &a,const vector<int> &b)
    {
        
    	return a[1] < b[1] || (a[1]==b[1] && a[0]<b[0]);//每个区间的第二个数字进行比较
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        
    	if(intervals.size() == 0)
    			return 0;
    	//sort()函数，默认的是对二维数组按照第一列的大小对每行的数组进行排序。
    	//所以可以加上cmp函数用按照任意列对数组进行排序
         sort(intervals.begin(), intervals.end(),cmp);
           int res = 0;
           //获取最小的区间终结点
            int las = intervals[0][1];
            for(int i = 1; i < intervals.size(); i++){
        
            //如果下一区间的起点 小于上一个区间的重点，说明有交集
                if(intervals[i][0] < las){
        
                 ++res;
                else{
        
                 las = intervals[i][1];//更新区间终结点
                 }   
            }
            return intervals.size()-cnt;
        }