从零开始写算法——贪心篇2：买卖股票的最佳时间 + 划分字母区间-开发者社区

在算法中，贪心算法 (Greedy Algorithm)往往是一个让人又爱又恨的话题。爱它是因为代码通常很短，恨它是因为“当前最优选择会导致全局最优”这个逻辑有时候很难一眼看穿。

今天我们通过两道经典的 LeetCode 题目——121. 买卖股票的最佳时机和763. 划分字母区间，来感受一下贪心算法如何在“一次遍历”中解决问题。

这两个题目虽然场景完全不同，但核心思想是通用的：维护一个关键的状态变量（最小值或最远边界），在遍历过程中不断更新这个状态，从而得到最终答案。

Part 1：买卖股票的最佳时机 —— 维护“历史最低点”

1. 题目核心

给定一个数组prices，它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

2. 贪心策略

我们要赚钱，核心逻辑非常简单：“低买高卖”。但是我们不能穿越时空，我们只能在当前这一天决定：

如果在今天卖出，我能赚多少？（取决于之前的最低价是多少）。
今天是不是一个新的“历史最低点”？如果是，那以后如果想买，肯定按今天的价格买更划算。

所以，我们需要维护一个变量min_price，代表过去几天（包括今天）出现的最低股价。

3. 代码实现 (C++)

你的代码中有一个非常有意思的注释，关于“先算利润还是先更新最小值”的讨论，这体现了很好的思考深度。

C++代码实现：

class Solution { public: int maxProfit(vector<int>& 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: vector<int> 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; // 不断更新，最后留下的就是最后一次出现的下标 } vector<int> 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数组通常不计入算法的空间复杂度，因为它用于存储结果）。