合并两个有序数组

问题

将两个非递减顺序排列的整数数组 nums1（有效长度 m）和 nums2（长度 n）合并，结果存储在 nums1 中并保持非递减顺序。nums1 总长度为 m+n，后 n 位初始为无效值。

代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int j = 0;
        int i = 0;
        vector<int> v;
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j])
                v.push_back(nums1[i++]);
            else
                v.push_back(nums2[j++]);
        }
        while (i < m) v.push_back(nums1[i++]);
        while (j < n) v.push_back(nums2[j++]);
        nums1 = v;
    }
};

我的代码的算法思想

1. 双指针归并：用 i 和 j 分别指向 nums1 和 nums2 的起始位置，比较元素大小，将较小值存入临时数组 v。
2. 剩余元素处理：当某一数组遍历完后，将另一数组剩余元素直接追加到 v。
3. 覆盖原数组：最终将临时数组 v 赋值给 nums1，完成原地替换。

算法思想的提炼（背诵用）

双指针+新建数组归并法：用两个指针遍历数组，按序存入临时数组，最后覆盖原数组。核心：空间换时间（O(m+n)），保留有序性。

移除元素

问题

给定数组 nums 和值 val，需原地移除所有等于 val 的元素（剩余元素顺序可变），返回非 val 元素的数量 k。要求前 k 个位置为非 val 元素，数组后续元素不限。

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        vector<int> new_nums;
        for (int num : nums) {
            if (num != val) new_nums.push_back(num);
        }
        nums = new_nums;
        return nums.size();
    }
};

我的代码的算法思想

1. 遍历筛选：新建临时数组，遍历原数组时将非 val 元素存入临时数组。
2. 覆盖原数组：用筛选后的临时数组直接替换原数组，实现"原地"修改。
3. 返回长度：临时数组的长度即为非 val 元素的数量 k。

算法思想的提炼（背诵用）

临时数组过滤法：遍历原数组筛选非 val 元素存入新数组，覆盖原数组实现"原地"操作。核心：空间换时间（O(n)），保证前 k 位有效。

删除有序数组中的重复项

问题

给定一个非严格递增排列的数组 nums，要求原地删除重复元素，使得每个元素只出现一次并保持相对顺序。返回唯一元素的个数 k，确保前 k 个元素为去重后的有序结果，数组后续元素不影响判定。

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;  // 指向去重后的数组的最后一个有效元素
        for (int j = 1; j < nums.size(); ++j) {
            if (nums[j] != nums[i]) {
                ++i;            // 移动i，表示下一个唯一元素的位置
                nums[i] = nums[j];  // 将新元素放到去重数组的正确位置
            }
        }
        return i + 1;  // 返回唯一元素的数量
    }
};

我的代码的算法思想

1. 双指针遍历：
   • 慢指针 i 记录去重后的有效序列末尾位置（初始为0）
   • 快指针 j 从1开始遍历数组，寻找与 nums[i] 不同的元素
2. 元素更新：
   • 当 nums[j] 与 nums[i] 不同时，先将 i 后移一位，再将 nums[j] 赋值给 nums[i]
3. 返回结果：
   • 最终 i+1 即为唯一元素的个数（因数组下标从0开始）

算法思想的提炼（背诵用）

快慢指针法：慢指针标记唯一序列末尾，快指针遍历数组；遇不同元素时更新慢指针并复制元素，保证前 k 项有序无重复。核心：双指针遍历（O(n)），空间复杂度 O(1)。

验证回文串

问题

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符后，短语正反读一致，则认为是回文串。给定字符串 s，判断是否为回文串。

代码

class Solution {
public:
    bool isPalindrome(string s) {
        string filtered = "";
        for (char c : s) {
            if (isalnum(c)) {
                filtered += tolower(c);
            }
        }

        int left = 0, right = filtered.size() - 1;
        while (left < right) {
            if (filtered[left] != filtered[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

我的代码的算法思想

1. 预处理过滤：
   • 遍历原字符串，筛选出字母数字字符并统一转为小写，生成新字符串 filtered
2. 双指针验证：
   • 左右指针分别从 filtered 的首尾向中间移动，逐个比较对称位置的字符
   • 若发现不匹配立即返回 false，否则最终返回 true

算法思想的提炼（背诵用）

预处理+双指针法：

1. 过滤非法字符并统一大小写，构建纯字母数字字符串
2. 双指针从两端向中心同步移动，验证对称性
   核心：两次线性遍历（时间复杂度 O(n)），需额外空间存储过滤后字符串（空间复杂度 O(n)）。

罗马数字转整数

问题

将罗马数字转换为整数。规则如下：

• 基本字符对应数值：I(1), V(5), X(10), L(50), C(100), D(500), M(1000)
• 特殊减法规则：
  • IV(4), IX(9)
  • XL(40), XC(90)
  • CD(400), CM(900)

代码

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> roman_to_int = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };

        int total = 0;
        for (int i = 0; i < s.length(); ++i) {
            int current_value = roman_to_int[s[i]];
            if (i + 1 < s.length() && current_value < roman_to_int[s[i + 1]]) {
                total -= current_value;
            }
            else {
                total += current_value;
            }
        }
        return total;
    }
};

我的代码的算法思想

1. 哈希映射预处理：
   • 用哈希表存储罗马字符与数值的对应关系
2. 逆向处理减法规则：
   • 遍历时比较当前字符与下一字符的值
   • 若当前值小于下一字符值（触发减法规则），则从总和减去当前值
   • 否则正常累加当前值

算法思想的提炼（背诵用）

逆向遍历法：

1. 哈希表存储字符映射，线性遍历字符串
2. 关键判断：若当前字符值小于后一字符值，说明触发减法规则（如IV=4），需减去当前值；否则正常累加
   核心：一次遍历处理所有情况（时间复杂度 O(n)），哈希表实现常数级查询（空间复杂度 O(1)）。

生命游戏

问题

根据细胞自动机规则，更新 m×n 网格中每个细胞状态：

1. 活细胞周围活细胞少于2个或超过3个时死亡
2. 活细胞周围有2-3个活细胞时存活
3. 死细胞周围正好3个活细胞时复活
   要求原地修改数组，且所有细胞状态需同步更新。

代码

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        int n = board[0].size();

        // 第一次遍历：标记状态变化
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int liveNeighbors = countLiveNeighbors(board, i, j, m, n);
                
                if (board[i][j] == 1) {  // 当前是活细胞
                    if (liveNeighbors < 2 || liveNeighbors > 3) 
                        board[i][j] = 2;  // 标记为即将死亡
                } else {                 // 当前是死细胞
                    if (liveNeighbors == 3) 
                        board[i][j] = 3;  // 标记为即将复活
                }
            }
        }

        // 第二次遍历：更新最终状态
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                board[i][j] = (board[i][j] == 2) ? 0 : 
                             (board[i][j] == 3) ? 1 : board[i][j];
            }
        }
    }

private:
    int countLiveNeighbors(const vector<vector<int>>& board, int i, int j, int m, int n) {
        int liveCount = 0;
        for (int x = -1; x <= 1; ++x) {
            for (int y = -1; y <= 1; ++y) {
                if (x == 0 && y == 0) continue;
                int ni = i + x, nj = j + y;
                if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                    // 统计当前实际存活的细胞（包含标记为2的活细胞）
                    if (board[ni][nj] == 1 || board[ni][nj] == 2) liveCount++;
                }
            }
        }
        return liveCount;
    }
};

我的代码的算法思想

1. 原地状态标记：
   • 使用2标记活细胞→死细胞，3标记死细胞→活细胞
   • 在统计邻居时，将标记为2的细胞视为仍存活（保证计算逻辑正确）
2. 两次遍历策略：
   • 第一次遍历：计算每个细胞的邻居数，按规则标记中间状态
   • 第二次遍历：将中间状态转换为最终状态（2→0，3→1）
3. 邻居统计优化：
   • 通过双重循环遍历八个方向，边界条件过滤无效坐标

算法思想的提炼（背诵用）

原地标记+两次遍历法：

1. 用特殊数字标记状态变化（2: 活→死，3: 死→活）
2. 第一次遍历计算邻居并标记中间状态，第二次遍历转换最终状态
   核心：通过中间状态避免同步更新冲突（时间复杂度 O(mn)，空间复杂度 O(1)）。

赎金信

问题

判断字符串 ransomNote 是否能由字符串 magazine 中的字符构成（每个字符在 magazine 中只能使用一次）。若可以则返回 true，否则返回 false。

代码

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> magazineCount;
        for (char c : magazine) {
            magazineCount[c]++;
        }

        for (char c : ransomNote) {
            if (magazineCount[c] > 0) {
                magazineCount[c]--;
            }
            else {
                return false;
            }
        }
        return true;
    }
};

我的代码的算法思想

1. 哈希表统计频率：
   • 遍历 magazine，用哈希表记录每个字符的出现次数
2. 字符可用性验证：
   • 遍历 ransomNote，检查每个字符是否在哈希表中有足够剩余次数
   • 若某个字符不足，立即返回 false；否则减少对应计数
3. 结果判定：
   • 若所有字符均满足条件，最终返回 true

算法思想的提炼（背诵用）

哈希计数法：

1. 统计 magazine 字符频次，遍历 ransomNote 时实时减少对应频次
2. 任一字符频次不足时立即终止，全部满足则成立
   核心：哈希表实现字符频次快速查询（时间复杂度 O(m + n)），空间复杂度 O(k)（k 为字符集大小）。

长度最小的子数组

问题

给定一个含 n 个正整数的数组和一个正整数 target，找出该数组中满足其总和大于等于 target 的长度最小的连续子数组，并返回其长度。若不存在则返回 0。

代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, sum = 0, min_len = INT_MAX;
        for (int right = 0; right < nums.size(); ++right) {
            sum += nums[right];
            while (sum >= target) { // 当sum满足条件时，尝试缩小窗口
                min_len = min(min_len, right - left + 1);
                sum -= nums[left++]; // 左指针右移，并更新sum
            }
        }
        return min_len == INT_MAX ? 0 : min_len;
    }
};

我的代码的算法思想

1. 滑动窗口法：
   • 使用双指针 left 和 right 表示窗口的左右边界，初始时 left = 0。
   • 右指针 right 遍历数组，累加元素值到 sum 中。
   • 当 sum >= target 时，进入循环收缩左边界：
     a. 更新最小长度 min_len 为当前窗口长度和 min_len 的较小值。
     b. 从 sum 中减去左边界元素的值，并将左指针右移。
2. 结果判断：
   • 遍历结束后，若 min_len 未被更新（仍为 INT_MAX），返回 0；否则返回 min_len。

算法思想的提炼（背诵用）

滑动窗口法：

1. 右指针扩展窗口，左指针收缩窗口，始终维护 sum >= target 的最小窗口长度。
2. 关键点：正整数组保证窗口扩展时和单调递增，收缩时能快速找到最短长度。
   核心：时间复杂度 O(n)（每个元素最多被访问两次），空间复杂度 O(1)。

逆波兰表达式求值

问题

根据逆波兰表示法（后缀表达式）计算算术表达式的值。运算符包括 +, -, *, /，除法需向零截断，且输入保证有效无除零。

代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (const string& token : tokens) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int a = s.top(); s.pop();
                int b = s.top(); s.pop();
                if (token == "+") s.push(b + a);
                else if (token == "-") s.push(b - a);
                else if (token == "*") s.push(b * a);
                else if (token == "/") s.push(b / a);
            } else {
                s.push(stoi(token));
            }
        }
        return s.top();
    }
};

我的代码的算法思想

1. 栈结构处理操作数：
   • 遍历每个 token，若为数字则转换为整数并入栈
   • 若为运算符，则弹出栈顶两个元素作为右操作数 a 和左操作数 b
2. 运算顺序处理：
   • 根据运算符类型对 b 和 a 进行相应运算（注意减法、除法需保持 b - a 和 b / a 的顺序）
   • 将运算结果压入栈中
3. 最终结果获取：
   • 遍历结束后，栈顶元素即为表达式计算结果

算法思想的提炼（背诵用）

栈模拟法：

1. 数字入栈，运算符弹出栈顶两元素运算后结果入栈
2. 关键顺序：先弹出右操作数，再弹出左操作数，确保 b [op] a 顺序正确（尤其减法和除法）
3. 除法处理：直接使用整数除法实现向零截断
   核心：线性遍历（时间复杂度 O(n)），栈辅助空间（空间复杂度 O(n)）。

反转链表 II

问题

反转链表中从位置 left 到 right（包含两端）的节点，要求仅遍历一趟完成局部反转，并保持其他节点原有顺序。

代码

class Solution {
public:
    ListNode* reverseList(ListNode* start, int length) {
        ListNode *prev = nullptr, *curr = start;
        for (int i = 0; i < length; ++i) { // 反转固定长度的链表段
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev; // 返回反转后的头节点
    }

    ListNode* getNode(ListNode* head, int steps) {
        ListNode* node = head;
        for (int i = 0; i < steps && node; ++i) {
            node = node->next;
        }
        return node; // 返回移动steps步后的节点
    }

    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* ahead = getNode(head, left - 1);    // 获取left前驱节点
        ListNode* leftNode = getNode(head, left);     // 原left节点
        ListNode* behind = getNode(head, right + 1); // right的后继节点
        
        ListNode* newHead = reverseList(leftNode, right - left + 1); // 反转局部链表
        
        if (ahead) {
            ahead->next = newHead;  // 前驱连接反转后的头
        } else {
            head = newHead;         // 若反转段包含原头节点，更新全局头
        }
        leftNode->next = behind;    // 反转后的尾节点连接后续节点
        return head;
    }
};

我的代码的算法思想

1. 定位关键节点：
   • 通过辅助函数 getNode 找到 left 的前驱节点 ahead 和 right 的后继节点 behind
   • leftNode 是原链表中待反转段的起始节点
2. 局部反转：
   • 调用 reverseList 反转 left 到 right 的链表段，返回反转后的头节点 newHead
3. 重连链表：
   • 若存在前驱节点 ahead，将其 next 指向 newHead
   • 将反转后的尾节点（原 leftNode）的 next 指向 behind
   • 若 left 为 1（无前驱），则更新全局头节点为 newHead

算法思想的提炼（背诵用）

四步定位法：

1. 定位前驱、反转段头、反转段尾、后继节点
2. 反转指定长度段，重连前驱与后继
   核心：一次遍历定位（时间复杂度 O(n)），空间复杂度 O(1)。

寻找峰值

问题

在整数数组中找到任意一个峰值元素的索引。峰值定义为严格大于左右相邻值的元素。假设 nums[-1] = nums[n] = -∞，要求时间复杂度为 O(log n)。

代码

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1)
        while (left + 1 < right) { // 区间内至少有两个元素时继续二分
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid; // 峰值可能在左半段或 mid 处
            } else {
                left = mid;  // 峰值必在右半段
            }
        }
        return right; // 最终 right 指向峰值
    }
};

我的代码的算法思想

1. 二分法变形：
   • 维护开区间 (left, right)，初始为 (-1, n-1)
   • 当区间长度大于1时，取中点 mid，比较 nums[mid] 与 nums[mid+1]
2. 方向决策：
   • 若 nums[mid] > nums[mid+1]：说明峰值可能在 mid 左侧或 mid 处，将 right 设为 mid
   • 若 nums[mid] < nums[mid+1]：说明右侧存在更大值，将 left 设为 mid
3. 终止条件：
   • 当 left + 1 >= right 时，区间仅含一个元素 right，即为峰值

算法思想的提炼（背诵用）

二分比较法：

1. 比较中点与右侧元素，向更大值方向缩小范围
2. 关键性质：若 nums[mid] < nums[mid+1]，则右侧必存在峰值；反之左侧或 mid 处存在峰值
   核心：每次二分排除一半区间（时间复杂度 O(log n)），空间复杂度 O(1)。

单词搜索

问题

在二维字符网格中判断是否存在由相邻单元格构成的路径，使得路径上的字符按顺序组成目标单词。每个单元格只能使用一次。

代码

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }

private:
    int rows, cols;
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int k) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != word[k]) 
            return false;
        if (k == word.size() - 1) 
            return true;
        
        char tmp = board[i][j];
        board[i][j] = '\0'; // 标记为已访问
        
        bool found = dfs(board, word, i + 1, j, k + 1) ||
                     dfs(board, word, i - 1, j, k + 1) ||
                     dfs(board, word, i, j + 1, k + 1) ||
                     dfs(board, word, i, j - 1, k + 1);
        
        board[i][j] = tmp; // 回溯恢复
        return found;
    }
};

我的代码的算法思想

1. 回溯法框架：
   • 遍历网格的每个单元格作为起点，尝试深度优先搜索（DFS）
   • 若某一起点的DFS找到完整路径，立即返回 true
2. DFS核心步骤：
   • 剪枝：越界或字符不匹配时终止当前路径
   • 终止条件：匹配到单词最后一个字符时返回成功
   • 标记访问：将当前单元格字符临时修改为特殊值（如 \0），防止重复使用
   • 四向探索：递归搜索上下左右四个方向
   • 回溯恢复：无论成功与否，恢复单元格原始字符以保证其他路径的正确性

算法思想的提炼（背诵用）

回溯+DFS法：

1. 遍历所有起点，通过DFS尝试构建路径
2. 关键操作：临时修改字符标记访问，回溯时恢复
3. 剪枝优化：及时终止无效路径（字符不匹配或越界）
   核心：时间复杂度 O(mn·4^L)（m、n为网格尺寸，L为单词长度），空间复杂度 O(L)（递归栈深度）。

直线上最多的点数

问题

给定平面上若干个点，求最多有多少个点位于同一条直线上。

代码

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) return n;
        int ans = 1;
        for (int i = 0; i < n; ++i) {
            unordered_map<string, int> slopeCount;
            int duplicates = 0;
            int maxCount = 0;
            for (int j = i + 1; j < n; ++j) {
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                if (dx == 0 && dy == 0) {
                    duplicates++;
                    continue;
                }
                int k = gcd(dx, dy);
                int reducedDx = dx / k;
                int reducedDy = dy / k;
                // 统一符号，使分母为正
                if (reducedDy < 0 || (reducedDy == 0 && reducedDx < 0)) {
                    reducedDx = -reducedDx;
                    reducedDy = -reducedDy;
                }
                string key = to_string(reducedDx) + "_" + to_string(reducedDy);
                slopeCount[key]++;
                maxCount = max(maxCount, slopeCount[key]);
            }
            ans = max(ans, maxCount + duplicates + 1);
        }
        return ans;
    }

private:
    int gcd(int a, int b) {
        a = abs(a);
        b = abs(b);
        if (b == 0) return a;
        return gcd(b, a % b);
    }
};

算法思想

1. 双重遍历基准点：以每个点 i 为基准，遍历其他所有点 j 计算相对坐标差 (dx, dy)。
2. 处理重复点：统计与基准点重合的点（dx=0 && dy=0），单独记录重复数 duplicates。
3. 最大公约数约分：用最大公约数约分 dx 和 dy，得到最简分数形式表示斜率。
4. 符号统一化：调整约分后的分母为正数，确保同一斜率的键唯一。例如，将 (1, -2) 转为 (-1, 2)。
5. 哈希统计频率：用哈希表统计各斜率出现的次数，维护最大值 maxCount。
6. 结果整合：最终点数为 maxCount + duplicates + 1（基准点自身）。

关键点

• 斜率唯一性处理：约分后统一符号避免不同形式表示同一斜率。
• 重复点处理：重合点不影响斜率统计，直接累加到所有可能直线。
• 边界处理：点数 ≤2 时直接返回结果，避免冗余计算。

算法复杂度

• 时间复杂度：O(n²)，双重遍历所有点对。
• 空间复杂度：O(n)，哈希表最多存储 O(n) 个斜率。

打家劫舍

问题

给定一个非负整数数组 nums，表示每个房屋的金额，不能同时偷相邻的房屋，求能偷窃的最大金额。

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> cache(n, -1);
        return dfs(n - 1, cache, nums);
    }

    int dfs(int i, vector<int>& cache, vector<int>& nums) {
        if (i < 0) return 0;  // 递归终止条件：无房屋可偷
        if (cache[i] != -1) return cache[i];  // 查缓存，避免重复计算
        
        // 状态转移：偷当前房屋（需跳过前一间）或不偷（沿用前一间的结果）
        int res = max(dfs(i - 1, cache, nums), dfs(i - 2, cache, nums) + nums[i]);
        cache[i] = res;  // 存储结果
        return res;
    }
};

算法思想

1. 动态规划（自顶向下）：从最后一个房屋开始，递归计算每个子问题的解，并通过缓存避免重复计算。
2. 状态转移方程：对于第 i 个房屋，最大金额为以下两者中的较大值：
   • 不偷第 i 个房屋：结果等于前 i-1 个房屋的最优解。
   • 偷第 i 个房屋：结果等于第 i 个房屋金额加上前 i-2 个房屋的最优解。
3. 递归终止条件：当 i < 0 时，无房屋可偷，返回 0。

关键点

• 记忆化缓存：通过 cache 数组存储已计算的结果，将时间复杂度从指数级优化为 O(n)。
• 重叠子问题处理：递归分解问题时，大量子问题被重复计算，缓存保证每个子问题只计算一次。

算法复杂度

• 时间复杂度：O(n)，每个房屋的状态只需计算一次。
• 空间复杂度：O(n)，递归调用栈和缓存数组各占用 O(n)。

股票最高利润

问题

给定股票每日价格数组 prices，只能进行一次买入和卖出（卖出在买入之后），求最大利润。若无法盈利则返回 0。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price = INT_MAX;   // 记录遍历过程中遇到的最低价格
        int max_profit = 0;        // 记录当前计算的最大利润

        for (int price : prices) {
            min_price = min(min_price, price);                 // 更新历史最低价
            max_profit = max(max_profit, price - min_price);   // 计算当前可能的最大利润
        }
        return max_profit;
    }
};

算法思想

贪心策略：在遍历价格的过程中，始终维护两个关键变量：

1. 历史最低价 min_price：表示截止到当前日期，股票的最低买入价格。
2. 当前最大利润 max_profit：表示在历史最低价买入、当前日期卖出所能获得的最大利润。

核心思路：对于每一天的股票价格，假设在这一天卖出，则最优的买入点一定是过去所有天数中的最低点。通过不断更新这两个变量，最终得到的 max_profit 即为全局最大利润。

关键点

• 更新时机：每遍历到一个新价格，都尝试更新历史最低价和最大利润。
• 数学保证：由于 max_profit 总是基于历史最低价计算，因此无需担心错过更优的买卖组合。例如，即使后续出现更低的价格，但若之后没有更高的卖出价，则不会影响已记录的最大利润。

示例分析

以输入 [7,1,5,3,6,4] 为例：

1. 第 2 天价格 1 更新为 min_price。
2. 第 5 天价格 6 时，计算利润 6-1=5，更新 max_profit=5。
3. 其他日期的利润均未超过 5，最终结果为 5。

算法复杂度

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(1)，仅用常数空间维护两个变量。

扩展思考

若允许多次买卖（但不能同时参与多笔交易），可参考“买卖股票的最佳时机 II”问题，采用动态规划或贪心策略解决。