LeetCode 剑指 Offer 63. 股票的最大利润

Categories:

题目描述
思路分析
1. 解法一：一次遍历（推荐）
相似题目

题目描述

✅ 剑指 Offer 63. 股票的最大利润

思路分析

解法一：一次遍历（推荐）

核心思路：

维护历史最低价格 minPrice。

当前利润为 price - minPrice，更新最大利润。

一次扫描即可完成。

复杂度分析：

时间复杂度：O(n)，其中 n 表示价格数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int ans = 0;

        for (int p : prices) {
            if (p < minPrice) {
                minPrice = p;
            } else {
                ans = Math.max(ans, p - minPrice);
            }
        }

        return ans;
    }
}

func maxProfit(prices []int) int {
	minPrice := int(^uint(0) >> 1)
	ans := 0

	for _, p := range prices {
		if p < minPrice {
			minPrice = p
		} else if p-minPrice > ans {
			ans = p - minPrice
		}
	}

	return ans
}

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	贪心
122. 买卖股票的最佳时机 II	简单	贪心
714. 买卖股票的最佳时机含手续费	中等	DP
309. 买卖股票的最佳时机含冷冻期	中等	DP
188. 买卖股票的最佳时机 IV	困难	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/75186789