algorithms►leetcode

033-买卖股票的最佳时机(贪心)

122. 买卖股票的最佳时机 II

问题描述

给定一个数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。你可以多次买卖这支股票，但必须在再次购买前卖出之前的股票。计算你能获得的最大利润。

示例

1
2
3
4
5
6
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 
- 第2天买入（1），第3天卖出（5），利润 = 5-1 = 4
- 第4天买入（3），第5天卖出（6），利润 = 6-3 = 3
总利润 = 4 + 3 = 7

方法一：贪心算法

核心思想

  • 只要今天的价格比昨天高，就进行交易（昨天买入，今天卖出）。
  • 因为可以多次交易，所有正利润的累加就是最大利润。

代码

1
2
3
4
5
6
7
8
9
var maxProfit = function(prices) {
    let profit = 0;
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
};

复杂度分析

  • 时间复杂度：O(n)，只需遍历一次数组。
  • 空间复杂度：O(1)，仅用常数空间。

方法二：动态规划

核心思想

  • 状态定义：
    • dp[i][0]：第 i 天结束时未持有股票的最大利润。
    • dp[i][1]：第 i 天结束时持有股票的最大利润。
  • 状态转移：
    • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
      （前一天未持有，或前一天持有今天卖出）
    • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
      （前一天持有，或前一天未持有今天买入）

代码

1
2
3
4
5
6
7
8
9
10
11
12
var maxProfit = function(prices) {
    const n = prices.length;
    const dp = new Array(n).fill(0).map(() => [0, 0]);
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
};

优化空间

1
2
3
4
5
6
7
8
9
10
var maxProfit = function(prices) {
    let [hold, notHold] = [-prices[0], 0];
    for (const p of prices) {
        [hold, notHold] = [
            Math.max(hold, notHold - p),
            Math.max(notHold, hold + p)
        ];
    }
    return notHold;
};

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)（优化后）。

方法对比

方法 时间复杂度 空间复杂度 适用场景
贪心 O(n) O(1) 简单高效，直接累加利润
动态规划 O(n) O(n) 或 O(1) 通用性强，可扩展性高

关键点总结

  1. 贪心算法：
    • 核心是 “所有正利润之和”，适用于本题的无限次交易。
  2. 动态规划：
    • 通过状态转移方程覆盖所有可能操作，适合更复杂的股票问题（如含手续费、冷冻期等）。

最终推荐

  • 直接使用贪心算法（代码简洁，效率高）：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    var maxProfit = function(prices) {
        let profit = 0;
        for (let i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    };
Frontend►JavaScript

015-async & await(语法糖)

Async/Await 详解（JavaScript）

async/await 是 ES2017 (ES8) 引入的异步编程语法糖，基于 Promise 实现，让异步代码的书写和阅读更接近同步方式，彻底解决了回调地狱问题。

核心概念

  1. async 函数

    • 声明一个异步函数：async function myFunc() { ... }
    • 返回值：总是返回一个 Promise 对象。
      • 函数内 return 的值会被包装成 Promise.resolve(value)
      • 抛出错误时返回 Promise.reject(error)
    1
    2
    3
    4
    async function foo() {
      return 42; // 等价于 Promise.resolve(42)
    }
    foo().then(console.log); // 输出 42

  2. await 表达式

    • 只能在 async 函数内部使用。
    • await promise：暂停当前 async 函数的执行，等待 Promise 完成。
      • 若 Promise 成功（fulfilled），返回 resolve 的值。
      • 若 Promise 失败（rejected），抛出错误（可用 try/catch 捕获）。
    1
    2
    3
    4
    5
    6
    7
    async function bar() {
      const result = await new Promise((resolve) => 
        setTimeout(() => resolve("完成!"), 1000)
      );
      console.log(result); // 1秒后输出 "完成!"
    }
    bar();

执行流程详解

1
2
3
4
5
6
7
8
9
10
async function example() {
  console.log("1: 开始");
  const data = await fetchData(); // 暂停，等待fetchData完成
  console.log(`3: 获取数据: ${data}`);
  return "处理完毕";
}

console.log("0: 调用前");
example().then(res => console.log(`4: 结果: ${res}`));
console.log("2: 调用后");

输出顺序：

0: 调用前
1: 开始
2: 调用后    // 主线程继续执行
3: 获取数据: ... // 异步恢复执行
4: 结果: 处理完毕

错误处理

使用 try/catch 捕获异常：

1
2
3
4
5
6
7
8
9
async function fetchWithError() {
  try {
    const data = await fetch("https://invalid-url");
    console.log(data);
  } catch (error) {
    console.error("请求失败:", error); // 捕获网络错误或reject
  }
}
fetchWithError();

关键优势

  1. 代码简洁：消除嵌套回调，线性化异步逻辑。
  2. 错误处理统一：使用 try/catch 替代 .catch()。
  3. 调试友好：可以在 await 行设置断点调试。
  4. 条件分支清晰：if/for 等逻辑可直接使用。

注意事项

  1. 顶层 await：
    ES2022 支持在模块顶层直接使用 await（仅限 ES Modules）：

    1
    2
    // 模块中
    const data = await fetchData(); // 合法

  2. 并行优化：
    多个独立异步操作应并行执行，避免串行等待：

    1
    2
    3
    4
    5
    6
    // 错误（串行）: 耗时 time1 + time2
    const r1 = await task1();
    const r2 = await task2();

    // 正确（并行）: 耗时 max(time1, time2)
    const [r1, r2] = await Promise.all([task1(), task2()]);

  3. 循环中的 await：
    在循环中需注意执行顺序：

    1
    2
    3
    4
    5
    6
    7
    // 顺序执行（串行）
    for (const url of urls) {
      await fetch(url); 
    }

    // 并行执行
    await Promise.all(urls.map(url => fetch(url)));

常见问题

Q: await 会阻塞主线程吗？
A: 不会！await 只是暂停当前 async 函数的执行，将控制权交还事件循环，主线程可继续处理其他任务。

Q: 能否在普通函数中用 await？
A: 不能！会抛出语法错误。只能在 async 函数内使用。

Q: async/await 会替代 Promise 吗？
A: 不会！它们是互补的：

  • async/await 用于控制异步流程
  • Promise 仍是异步操作的底层基础

总结

async/await 是 JavaScript 异步编程的革命性改进：

  1. 用同步写法实现异步逻辑
  2. 基于 Promise，兼容现有异步库
  3. 错误处理更符合直觉
  4. 大幅提升代码可读性和可维护性

最佳实践：所有返回 Promise 的函数都可用 await 调用，配合 try/catch 处理错误，用 Promise.all() 优化并行任务。