在算法中贪心算法 (Greedy Algorithm)往往是一个让人又爱又恨的话题。爱它是因为代码通常很短恨它是因为“当前最优选择会导致全局最优”这个逻辑有时候很难一眼看穿。今天我们通过两道经典的 LeetCode 题目——121. 买卖股票的最佳时机和763. 划分字母区间来感受一下贪心算法如何在“一次遍历”中解决问题。这两个题目虽然场景完全不同但核心思想是通用的维护一个关键的状态变量最小值或最远边界在遍历过程中不断更新这个状态从而得到最终答案。Part 1买卖股票的最佳时机 —— 维护“历史最低点”1. 题目核心给定一个数组prices它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易即买入和卖出一支股票一次设计一个算法来计算你所能获取的最大利润。2. 贪心策略我们要赚钱核心逻辑非常简单“低买高卖”。 但是我们不能穿越时空我们只能在当前这一天决定如果在今天卖出我能赚多少取决于之前的最低价是多少。今天是不是一个新的“历史最低点”如果是那以后如果想买肯定按今天的价格买更划算。所以我们需要维护一个变量min_price代表过去几天包括今天出现的最低股价。3. 代码实现 (C)你的代码中有一个非常有意思的注释关于“先算利润还是先更新最小值”的讨论这体现了很好的思考深度。C代码实现class Solution { public: int maxProfit(vectorint prices) { // 思路就是我们通过一次遍历但是这个遍历中我们去维护最小值以及更新答案 // min_price 初始化为第一天的价格 int ans 0, min_price prices[0]; for (int x : prices) { /* 这里有一个细节逻辑 我们是先计算 ans max(ans, x - min_price)再更新 min_price。 这意味着我们计算的是【今天的价格 - 之前几天的最低价】。 如果你反过来先更新 min_price再算 ans 那么计算的就是【今天的价格 - 包括今天在内的历史最低价】。 如果今天就是最低价利润算出来是 0反正 ans 初始化也是 0 所以这两种写法对最终结果 ans 没有影响。 */ ans max(ans, x - min_price); min_price min(min_price, x); } return ans; } };4. 复杂度分析时间复杂度O(N)我们只用了一个for循环遍历数组prices每个元素只访问了一次。空间复杂度O(1)我们只使用了ans和min_price两个整数变量不需要额外的数组空间。Part 2划分字母区间 —— 维护“最远边界”1. 题目核心给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。 例如ababcbacadefegdehijhklij。a出现在最前面也出现在下标 8 的位置。那么第一个片段至少要切在下标 8 之后否则a就跨越两个片段了。2. 贪心策略这道题的贪心逻辑在于一旦由于某个字母比如 a被迫扩大了区间这个区间内的所有其他字母比如 b, c也得被包进来。我们可以把这个问题分解为两个步骤预处理每个人都想知道自己“最后出现的位置”在哪里。我们可以先遍历一遍记下每个字母最后一次出现的下标。合并区间我们维护一个end指针表示当前片段至少要延伸到的位置。当我们遍历到一个字符c时看看它的最后出现位置是不是比当前的end还远如果是为了包住这个c我们的片段必须延长end变大。何时收网当遍历下标i追上了end时说明这一段里所有出现过的字母它们的最后一次出现位置都在i之前或就是i。此刻我们可以安全地切一刀3. 代码实现 (C)这一段代码完美诠释了“二次遍历”的思想。C代码实现class Solution { // 思路 同一个字母最多出现在一个片段中意味这个区间要包含所有这个字母所以需要对区间进行划分 // 先计算每个字母对应下标然后划分出区间然而区间内的其他字母也会有自己对应的区间此时应该进行合并区间 // 也就是我们目标两次遍历第一次预处理第二次进行划分。 public: vectorint partitionLabels(string s) { int n s.size(); // last 数组用来充当哈希表记录每个字符最后出现的下标 // 大小为 26对应 a-z int last[26]; for (int i 0; i n; i) { last[s[i] - a] i; // 不断更新最后留下的就是最后一次出现的下标 } vectorint ans; int start 0, end 0; // 第二次遍历根据最远边界进行切割 for (int i 0; i n; i) { // 贪心核心end 必须能包住当前字符 s[i] 的最后出现位置 end max(end, last[s[i] - a]); // 如果当前的遍历下标 i 追上了 end说明当前片段可以结束了 if(end i) { ans.push_back(end - start 1); // 计算当前片段长度 start i 1; // 更新下一个片段的起点 } } return ans; } };4. 复杂度分析时间复杂度O(N)虽然有两个for循环但它们是并列的不是嵌套的。第一个循环遍历N次构建last数组。第二个循环遍历N次进行切割。总操作次数是2N在渐进复杂度中依然是 O(N)。空间复杂度O(1)虽然我们开辟了一个last数组但它的大小固定为 26字符集大小不随字符串长度N变化。在算法分析中常数大小的空间视为 O(1)。注返回值的ans数组通常不计入算法的空间复杂度因为它用于存储结果。总结这两道题虽然外表不同但本质上都是线性扫描 状态更新买卖股票我们在扫描中更新最小值 (min)一旦遇到高价就计算利润。划分字母我们在扫描中更新最远边界 (end)一旦到达边界就进行切割。这种“走一步看一步”且只需一次或两次遍历的方法正是贪心算法在处理线性数据结构时的强大之处。掌握这种思维能让你在面试中快速写出 O(N) 的高效代码。