[LeetCode] 121. Best Time to Buy and Sell Stock

Easy
Related Topics: Array / Dynamic Programming
LeetCode Source

解题想法

当下想到最直觉的解法，一个变数 min_index 纪录最小值的位置，i 用来寻访每个的 prices 的值

for loop 里头判断式用来找寻最佳解

Python

class Solution:    def maxProfit(self, prices: List[int]) -> int:        min_index, res = 0, 0        for i in range(1, len(prices)):            if prices[i] < prices[min_index]:                min_index = i            if i > min_index and prices[i] - prices[min_index] > res:                res = prices[i] - prices[min_index]        return res

C++

class Solution {public:    int maxProfit(vector<int>& prices) {        int res = 0, min_index = 0;        for (int i = 1; i < prices.size(); i++) {            if (prices[i] < prices[min_index])                min_index = i;            if (i > min_index && prices[i] - prices[min_index] > res)                res = prices[i] - prices[min_index];        }        return res;    }};

这系列文被记录在 Top Interview 150 Series