【贪心算法】(经典实战应用解析(二)

在贪心算法的学习过程中,数组类问题是非常重要的一类应用场景.很多题目表面上看只是简单的遍历、比较和更新，但真正的核心在于:如何在每一步选择中保留对后续最有利的状态.这也正是贪心算法区别于普通模拟的关键所在.在上一篇内容中,我们已经通过一些经典题目初步了解了贪心算法在找零、排序、优先队列和趋势判断中的应用.本文将继续围绕贪心算法展开,重点分析一组与 递增序列 和 股票买卖 相关的经典实战题目,包括:最长递增子序列、递增的三元子序列、最长连续递增序列、买卖股票的最佳时机、买卖股票的最佳时机 II.这些题目虽然都可以从数组遍历入手,但背后的贪心策略并不完全相同.例如,在递增序列问题中,我们往往需要维护一个更小、更有潜力的结尾值,为后续元素创造更多连接机会;在连续递增序列问题中,则需要抓住相邻元素之间的变化趋势;而在股票买卖问题中,贪心思想体现为寻找最低买入点、捕捉上涨区间,或者将每一段可获得的利润及时累加.通过本文的讲解,我们不仅会分析每道题的解题思路和代码实现,还会重点理解其中的贪心选择依据:为什么当前这样更新是最优的?为什么不会影响后续结果?局部最优又是如何逐步转化为最终答案的?希望通过这几道经典题目的实战解析,能够帮助大家进一步掌握贪心算法在数组问题中的常见套路,建立起从题意分析到贪心策略设计的完整思维过程,为后续解决更多复杂的最优解问题打下基础.废话不多说,下面跟着小编的节奏一起去疯狂的学习吧!

1.最长递增子序列(OJ题)

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

核心代码

class Solution { public:    //函数功能：返回数组nums的最长严格递增子序列的长度    int lengthOfLIS(vector<int>& nums)    {        //获取数组的总长度        int n = nums.size();        //核心数组ret：        //存储【长度为 i 的最长递增子序列的最小末尾元素】        //贪心思想：末尾越小，后续越容易接更长的子序列        vector<int> ret;        //初始化：将数组第一个元素放入结果数组        ret.push_back(nums[0]);        //从第二个元素开始遍历整个数组        for(int i = 1; i < n; i++)        {            //情况1：当前数字 > ret的最后一个元素            //说明可以直接接在最长子序列后面，长度+1            if(nums[i] > ret.back())            {                ret.push_back(nums[i]);            }            //情况2：当前数字 <= ret的最后一个元素            //用二分查找找到ret中第一个 >= 当前数的位置，替换它            else            {                //二分查找的左右边界                int left = 0, right = ret.size() - 1;                //二分查找：找到第一个大于等于nums[i]的元素下标                while(left < right)                {                    //等价于 mid = (left + right) / 2，右移运算效率更高                    int mid = (left + right) >> 1;                    //中间值 < 当前数，说明目标在右半区间                    if(ret[mid] < nums[i])                        left = mid + 1;                    //中间值 >= 当前数，目标在左半区间                    else                        right = mid;                }                //替换该位置元素，维持ret数组的单调性，优化后续子序列                ret[left] = nums[i];            }        }        //ret数组的长度 就是 最长递增子序列的长度        return ret.size();    } };

完整测试代码

#include <iostream> #include <vector> using namespace std; class Solution { public:    // 函数功能：返回数组 nums 的最长严格递增子序列的长度    int lengthOfLIS(vector<int>& nums)    {        // 获取数组的总长度        int n = nums.size();        // 边界情况：空数组没有递增子序列        if (n == 0)            return 0;        // 核心数组 ret：        // 存储【长度为 i 的最长递增子序列的最小末尾元素】        // 贪心思想：末尾越小，后续越容易接更长的子序列        vector<int> ret;        // 初始化：将数组第一个元素放入结果数组        ret.push_back(nums[0]);        // 从第二个元素开始遍历整个数组        for (int i = 1; i < n; i++)        {            // 情况1：当前数字 > ret 的最后一个元素            // 说明可以直接接在最长子序列后面，长度 +1            if (nums[i] > ret.back())            {                ret.push_back(nums[i]);            }                // 情况2：当前数字 <= ret 的最后一个元素                // 用二分查找找到 ret 中第一个 >= 当前数的位置，替换它            else            {                int left = 0, right = ret.size() - 1;                // 二分查找：找到第一个大于等于 nums[i] 的元素下标                while (left < right)                {                    int mid = (left + right) >> 1;                    if (ret[mid] < nums[i])                        left = mid + 1;                    else                        right = mid;                }                // 替换该位置元素，维持 ret 数组的单调性                ret[left] = nums[i];            }        }        // ret 数组的长度就是最长递增子序列的长度        return ret.size();    } }; void printVector(const vector<int>& nums) {    cout << "[";    for (size_t i = 0; i < nums.size(); i++)    {        cout << nums[i];        if (i != nums.size() - 1)            cout << ", ";    }    cout << "]"; } int main() {    Solution sol;    vector<vector<int>> testCases = {            {10, 9, 2, 5, 3, 7, 101, 18},  // 普通情况，结果为 4            {0, 1, 0, 3, 2, 3},            // 包含重复和回落，结果为 4            {7, 7, 7, 7, 7, 7, 7},         // 全部相等，结果为 1            {1, 2, 3, 4, 5, 6},            // 严格递增，结果为 6            {6, 5, 4, 3, 2, 1},            // 严格递减，结果为 1            {1},                           // 单个元素，结果为 1            {},                            // 空数组，结果为 0            {4, 10, 4, 3, 8, 9},           // 常见测试，结果为 3            {2, 5, 1, 8, 3, 9, 4},         // 多次替换 ret 元素，结果为 4            {-1, 3, 4, -2, 0, 6, 2, 3}     // 包含负数，结果为 4    };    for (int i = 0; i < testCases.size(); i++)    {        vector<int> nums = testCases[i];        cout << "测试用例 " << i + 1 << "：";        printVector(nums);        cout << endl;        cout << "最长递增子序列长度：";        cout << sol.lengthOfLIS(nums) << endl;        cout << "------------------------" << endl;    }    return 0; }

2.递增的三元子序列(OJ题)

解法(贪心):
贪心策略:最长递增子序列的简化版.不用一个数组存  数据              ,仅需两个变量即可.也不用二分插入位置,仅需两次比较就可以找到插入位置.

核心代码

class Solution { public:    //函数功能：返回数组是否存在递增三元子序列    bool increasingTriplet(vector<int>& nums)    {        //边界：数组长度小于3直接返回false        if(nums.size() < 3) return false;        //a：记录遍历过程中【最小的第一个数】        //b：记录遍历过程中【第二小的第二个数】        //初始化：a为数组第一个元素，b为整型最大值（初始无第二大数）        int a = nums[0], b = INT_MAX;        //从数组第二个元素开始遍历        for(int i = 1; i < nums.size(); i++)        {            //情况1：当前数字 > b → 找到满足条件的三元组 a < b < nums[i]，直接返回true            if(nums[i] > b)                return true;            //情况2：当前数字 > a 且 ≤ b → 更新b为更小的值，更易找到第三个数            else if(nums[i] > a)                b = nums[i];            //情况3：当前数字 ≤ a → 更新a为更小的值，优化后续匹配            else                a = nums[i];        }        //遍历结束未找到，返回false        return false;    } };

完整测试代码

#include <iostream> #include <vector> #include <climits> using namespace std; class Solution { public:    // 函数功能：返回数组是否存在递增三元子序列    bool increasingTriplet(vector<int>& nums)    {        // 边界：数组长度小于 3 直接返回 false        if (nums.size() < 3)            return false;        // a：记录遍历过程中【最小的第一个数】        // b：记录遍历过程中【第二小的第二个数】        int a = nums[0], b = INT_MAX;        // 从数组第二个元素开始遍历        for (int i = 1; i < nums.size(); i++)        {            // 情况1：当前数字 > b            // 找到满足条件的三元组 a < b < nums[i]            if (nums[i] > b)                return true;                // 情况2：当前数字 > a 且 <= b                // 更新 b 为更小的值，更容易找到第三个数            else if (nums[i] > a)                b = nums[i];                // 情况3：当前数字 <= a                // 更新 a 为更小的值，优化后续匹配            else                a = nums[i];        }        // 遍历结束未找到，返回 false        return false;    } }; void printVector(const vector<int>& nums) {    cout << "[";    for (size_t i = 0; i < nums.size(); i++)    {        cout << nums[i];        if (i != nums.size() - 1)            cout << ", ";    }    cout << "]"; } void printBool(bool result) {    cout << (result ? "true" : "false"); } int main() {    Solution sol;    vector<vector<int>> testCases = {            {1, 2, 3, 4, 5},          // 存在递增三元子序列：1,2,3            {5, 4, 3, 2, 1},          // 不存在            {2, 1, 5, 0, 4, 6},       // 存在：0,4,6            {1, 1, 1, 1},             // 全部相等，不存在            {1, 2},                   // 长度小于 3，不存在            {},                       // 空数组，不存在            {2, 4, -2, -3},           // 不存在            {20, 100, 10, 12, 5, 13}, // 存在：10,12,13            {1, 5, 0, 4, 1, 3},       // 存在：0,1,3            {5, 1, 5, 5, 2, 5, 4},    // 存在：1,2,5            {2, 1, 5, 0, 3},          // 不存在            {-1, 0, 1},               // 存在：-1,0,1            {1, 2, 2, 2, 3}           // 存在：1,2,3    };    for (int i = 0; i < testCases.size(); i++)    {        vector<int> nums = testCases[i];        cout << "测试用例 " << i + 1 << "：";        printVector(nums);        cout << endl;        cout << "是否存在递增三元子序列：";        printBool(sol.increasingTriplet(nums));        cout << endl;        cout << "------------------------" << endl;    }    return 0; }

3.最长连续递增序列(OJ题)

解法(贪心):
贪心策略:找到以某个位置为起点的最长连续递增序列之后(设这个序列的末尾为 j 位置),接下来直接以 j + 1 的位置为起点寻找下一个最长连续递增序列.

核心代码

class Solution { public:    //函数功能：返回最长连续递增子序列的长度    int findLengthOfLCIS(vector<int>& nums)    {        //ret：记录最终的最长连续递增子序列长度        //n：数组的总长度        int ret = 0, n = nums.size();        //i 作为连续递增区间的起始位置，不写i++，手动更新起始位置        for(int i = 0; i < n; )        {            //j 从i的下一位开始，寻找当前递增区间的结束位置            int j = i + 1;            //循环判断：如果j不越界，且后一个数 > 前一个数，说明连续递增，j继续后移            while(j < n && nums[j] > nums[j - 1])                j++;            //计算当前连续递增区间的长度(j-i)，更新最大值            ret = max(ret, j - i);            //关键：将下一个区间的起始位置i 直接跳到 j，跳过已遍历的区间，优化效率            i = j;        }        //返回最终的最长长度        return ret;    } };

完整测试代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public:    // 函数功能：返回最长连续递增子序列的长度    int findLengthOfLCIS(vector<int>& nums)    {        // ret：记录最终的最长连续递增子序列长度        // n：数组的总长度        int ret = 0, n = nums.size();        // i 作为连续递增区间的起始位置，不写 i++，手动更新起始位置        for (int i = 0; i < n; )        {            // j 从 i 的下一位开始，寻找当前递增区间的结束位置            int j = i + 1;            // 如果 j 不越界，且后一个数 > 前一个数，说明连续递增            while (j < n && nums[j] > nums[j - 1])                j++;            // 计算当前连续递增区间的长度            ret = max(ret, j - i);            // 将下一个区间的起始位置 i 直接跳到 j            i = j;        }        return ret;    } }; void printVector(const vector<int>& nums) {    cout << "[";    for (size_t i = 0; i < nums.size(); i++)    {        cout << nums[i];        if (i != nums.size() - 1)            cout << ", ";    }    cout << "]"; } int main() {    Solution sol;    vector<vector<int>> testCases = {            {1, 3, 5, 4, 7},              // 最长连续递增：[1,3,5]，长度 3            {2, 2, 2, 2, 2},              // 全部相等，长度 1            {1, 2, 3, 4, 5},              // 整体递增，长度 5            {5, 4, 3, 2, 1},              // 整体递减，长度 1            {1},                          // 单个元素，长度 1            {},                           // 空数组，长度 0            {1, 3, 5, 7},                 // 全部连续递增，长度 4            {7, 1, 2, 3, 0, 4, 5, 6},     // 多段递增，最长长度 4            {1, 2, 2, 3, 4, 1, 2, 3, 4},  // 包含重复元素，最长长度 4            {-3, -2, -1, 0, -1, 1, 2},    // 包含负数，最长长度 4            {10, 20, 30, 5, 10, 15, 20},  // 后半段更长，最长长度 4            {3, 4, 5, 1, 2, 3, 4, 0}      // 中间一段最长，长度 4    };    for (int i = 0; i < testCases.size(); i++)    {        vector<int> nums = testCases[i];        cout << "测试用例 " << i + 1 << "：";        printVector(nums);        cout << endl;        cout << "最长连续递增子序列长度：";        cout << sol.findLengthOfLCIS(nums) << endl;        cout << "------------------------" << endl;    }    return 0; }

4.买卖股票的最佳时机(OJ题)

解法(贪心):
贪心策略:由于只能交易一次,所以对于某一个位置 i,要想获得最大利润,仅需知道前面所有元素的最小值.然后在最小值的位置买入股票,在当前位置卖出股票即可.

核心代码

class Solution { public:    //函数功能：传入股票价格数组，返回最大利润（无利润则返回0）    int maxProfit(vector<int>& prices)    {        //ret：存储最终的最大利润，初始化为0（不交易时利润为0）        int ret = 0;        //遍历数组：        //i：遍历下标        //prevMin：记录【遍历到当前位置之前】的最低股票价格，初始化为整型最大值        for(int i = 0, prevMin = INT_MAX; i < prices.size(); i++)        {            //核心步骤1：计算【当天价格 - 之前的最低价】，更新最大利润            //必须先算利润，再更新最小值！保证用的是「之前」的最低价            ret = max(ret, prices[i] - prevMin);            //核心步骤2：更新「遍历过的价格中的最小值」，为下一天计算利润做准备            prevMin = min(prevMin, prices[i]);        }        //返回最大利润        return ret;    } };

完整测试代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public:    // 函数功能：传入股票价格数组，返回最大利润（无利润则返回 0）    int maxProfit(vector<int>& prices)    {        // 边界情况：没有股票价格，无法交易        if (prices.empty())            return 0;        // ret：存储最终的最大利润，初始化为 0（不交易时利润为 0）        int ret = 0;        // prevMin：记录遍历到当前位置之前的最低股票价格        int prevMin = prices[0];        // 从第二天开始遍历        for (int i = 1; i < prices.size(); i++)        {            // 核心步骤1：计算当天卖出可以获得的利润            ret = max(ret, prices[i] - prevMin);            // 核心步骤2：更新历史最低买入价格            prevMin = min(prevMin, prices[i]);        }        // 返回最大利润        return ret;    } }; void printVector(const vector<int>& nums) {    cout << "[";    for (size_t i = 0; i < nums.size(); i++)    {        cout << nums[i];        if (i != nums.size() - 1)            cout << ", ";    }    cout << "]"; } int main() {    Solution sol;    vector<vector<int>> testCases = {            {7, 1, 5, 3, 6, 4},       // 最低 1 买入，最高 6 卖出，利润 5            {7, 6, 4, 3, 1},          // 一直下跌，利润 0            {1, 2, 3, 4, 5},          // 一直上涨，利润 4            {2, 4, 1},                // 2 买入，4 卖出，利润 2            {3, 3, 3, 3},             // 价格不变，利润 0            {1},                      // 只有一天，无法交易，利润 0            {},                       // 空数组，利润 0            {5, 1, 2, 10, 3, 12},     // 1 买入，12 卖出，利润 11            {10, 7, 5, 8, 11, 9},     // 5 买入，11 卖出，利润 6            {2, 1, 2, 0, 1}           // 1 买入，2 卖出，利润 1    };    for (int i = 0; i < testCases.size(); i++)    {        vector<int> prices = testCases[i];        cout << "测试用例 " << i + 1 << "：";        printVector(prices);        cout << endl;        cout << "最大利润：";        cout << sol.maxProfit(prices) << endl;        cout << "------------------------" << endl;    }    return 0; }

5.买卖股票的最佳时机II(OJ题)

解法(贪心):
贪心策略:由于可以进行无限次交易,所以只要是一个上升区域,我们就把利润拿到手就好了.

核心代码

//解法一：双指针法 - 找到完整的上涨区间，一次性计算利润 class Solution { public:    //函数功能：传入股票价格数组，返回最大利润    int maxProfit(vector<int>& p)    {        //ret：累计总利润        //n：数组长度        int ret = 0, n = p.size();        //遍历数组，i 标记【买入点】        for(int i = 0; i < n; i++)        {            //j 从 i 出发，寻找当前上涨区间的【卖出点】            int j = i;            //循环：只要后一天价格更高，就继续持有，j 后移            while(j + 1 < n && p[j + 1] > p[j])                j++;            //计算当前完整上涨区间的利润，累加到总利润            ret += p[j] - p[i];            //关键：i 直接跳转到 j，跳过已遍历的上涨区间，开始寻找下一个上涨段            i = j;        }        //返回总利润        return ret;    } };

完整测试代码

#include <iostream> #include <vector> using namespace std; // 解法一：双指针法 - 找到完整的上涨区间，一次性计算利润 class Solution { public:    // 函数功能：传入股票价格数组，返回最大利润    int maxProfit(vector<int>& p)    {        // ret：累计总利润        // n：数组长度        int ret = 0, n = p.size();        // 遍历数组，i 标记【买入点】        for (int i = 0; i < n; i++)        {            // j 从 i 出发，寻找当前上涨区间的【卖出点】            int j = i;            // 只要后一天价格更高，就继续持有，j 后移            while (j + 1 < n && p[j + 1] > p[j])                j++;            // 计算当前完整上涨区间的利润，累加到总利润            ret += p[j] - p[i];            // i 直接跳转到 j，跳过已遍历的上涨区间            i = j;        }        // 返回总利润        return ret;    } }; void printVector(const vector<int>& nums) {    cout << "[";    for (size_t i = 0; i < nums.size(); i++)    {        cout << nums[i];        if (i != nums.size() - 1)            cout << ", ";    }    cout << "]"; } int main() {    Solution sol;    vector<vector<int>> testCases = {            {7, 1, 5, 3, 6, 4},       // 两段上涨：1->5，3->6，总利润 7            {1, 2, 3, 4, 5},          // 一直上涨：1->5，利润 4            {7, 6, 4, 3, 1},          // 一直下跌：利润 0            {3, 3, 3, 3},             // 价格不变：利润 0            {1},                      // 只有一天：利润 0            {},                       // 空数组：利润 0            {2, 1, 2, 0, 1},          // 两段上涨：1->2，0->1，总利润 2            {6, 1, 3, 2, 4, 7},       // 两段上涨：1->3，2->7，总利润 7            {1, 3, 2, 8, 4, 9},       // 三段上涨：1->3，2->8，4->9，总利润 13            {5, 4, 5, 6, 1, 2, 3},    // 两段上涨：4->6，1->3，总利润 4            {10, 20, 15, 25, 5, 30},  // 三段上涨：10->20，15->25，5->30，总利润 45            {1, 2, 2, 3, 4}           // 平台后继续上涨：1->2，2->4，总利润 3    };    for (int i = 0; i < testCases.size(); i++)    {        vector<int> prices = testCases[i];        cout << "测试用例 " << i + 1 << "：";        printVector(prices);        cout << endl;        cout << "最大利润：";        cout << sol.maxProfit(prices) << endl;        cout << "------------------------" << endl;    }    return 0; }

核心代码

//解法二：逐日拆分法 - 极简贪心，只赚每一天的上涨差价 class Solution { public:    int maxProfit(vector<int>& prices)    {        //总利润初始化为0        int ret = 0;        //从第二天开始遍历（对比前一天价格）        for(int i = 1; i < prices.size(); i++)        {            //核心贪心：只要今天价格 > 昨天价格，就赚取这一天的差价            if(prices[i] > prices[i - 1])                ret += prices[i] - prices[i - 1];        }        //所有小利润之和 = 最大总利润        return ret;    } };

完整测试代码

#include <iostream> #include <vector> using namespace std; // 解法二：逐日拆分法 - 极简贪心，只赚每一天的上涨差价 class Solution { public:    int maxProfit(vector<int>& prices)    {        // 总利润初始化为 0        int ret = 0;        // 从第二天开始遍历，对比前一天价格        for (int i = 1; i < prices.size(); i++)        {            // 核心贪心：只要今天价格 > 昨天价格，就赚取这一天的差价            if (prices[i] > prices[i - 1])                ret += prices[i] - prices[i - 1];        }        // 所有小利润之和 = 最大总利润        return ret;    } }; void printVector(const vector<int>& nums) {    cout << "[";    for (size_t i = 0; i < nums.size(); i++)    {        cout << nums[i];        if (i != nums.size() - 1)            cout << ", ";    }    cout << "]"; } int main() {    Solution sol;    vector<vector<int>> testCases = {            {7, 1, 5, 3, 6, 4},       // 上涨差价：(5-1) + (6-3) = 7            {1, 2, 3, 4, 5},          // 每天都上涨，总利润 4            {7, 6, 4, 3, 1},          // 一直下跌，总利润 0            {3, 3, 3, 3},             // 价格不变，总利润 0            {1},                      // 只有一天，无法交易，利润 0            {},                       // 空数组，利润 0            {2, 1, 2, 0, 1},          // (2-1) + (1-0) = 2            {6, 1, 3, 2, 4, 7},       // (3-1) + (4-2) + (7-4) = 7            {1, 3, 2, 8, 4, 9},       // (3-1) + (8-2) + (9-4) = 13            {5, 4, 5, 6, 1, 2, 3},    // (5-4) + (6-5) + (2-1) + (3-2) = 4            {10, 20, 15, 25, 5, 30},  // (20-10) + (25-15) + (30-5) = 45            {1, 2, 2, 3, 4}           // (2-1) + (3-2) + (4-3) = 3    };    for (int i = 0; i < testCases.size(); i++)    {        vector<int> prices = testCases[i];        cout << "测试用例 " << i + 1 << "：";        printVector(prices);        cout << endl;        cout << "最大利润：";        cout << sol.maxProfit(prices) << endl;        cout << "------------------------" << endl;    }    return 0; }