买卖股票的最佳时机

题意

给定每日股价，求一次买卖的最大利润。

思路

扫描到第 i 天时，只需知道前 i-1 天的最低价 min_price，今天卖出的利润就是 prices[i] - min_price。更新 min_price 和最大利润即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int mn = INT_MAX, ans = 0;
        for (int x : prices) {
            mn = min(mn, x);
            ans = max(ans, x - mn);
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().maxProfit(a) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#!/usr/bin/env python3
from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        mn, ans = float("inf"), 0
        for x in prices:
            mn = min(mn, x)
            ans = max(ans, x - mn)
        return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().maxProfit(a))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。

总结

只需维护一个变量"此前最低价"，每步计算当天卖出的利润。贪心正确性：最大利润一定在某天卖出，而最优买入日一定是此前最低价日。

买卖股票的最佳时机

目录

题意

思路

代码

复杂度

总结