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

前言

　　究竟何时才是买卖股票的最好时机呢? 这题逻辑很生活化，就是把一个阵列内所有的价格遍历完，低买高卖后把最大的差价回传出来，这题使用了单迴圈遍历阵列里所有的价格，遍历里也是常数的时间操作，时间複杂度推算可以达到 O(n)，这篇有 Java 和 Python 的写法。

题目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

给你一个价格阵列 prices ，prices[i] 是取得一个股票在第 i 天的价格。

你想要最大化你的利润，藉着选择一天去买一张股票和选择在未来不同天里去卖掉那张股票。

你可以从这个交易回传最大化的利润。如果你无法达到任何利润，就回传 0。

题目连结：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

题目限制

注意：不能在第二天买入后第一天卖出，必须先买后卖。

1 <= prices.length <= 105
0 <= prices[i] <= 104

範例

Input: prices = [7,1,5,3,6,4]Output: 5Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Input: prices = [7,6,4,3,1]Output: 0Explanation: In this case, no transactions are done and the max profit = 0.

思路&笔记

判断阵列中值的大小，把更小的值存起来两数的相差 = 把当前的索引的值 - 上一个索引的值比较前一个值，将比较大的值存入

JAVA 实现

class Solution {    public int maxProfit(int[] prices) {                int min = Integer.MAX_VALUE;  // 整数类型中的最大值 2³¹        int op = 0;        int pist = 0;                for(int i = 0; i < prices.length; i++){                        // 找到阵列中最小的值            if(prices[i] < min){                min = prices[i]; // 前一个索引的值(最小的值)            }                        // 两数的相差 = 当前索引的值 - 前一个索引的值(最小的值)            pist = prices[i] - min;                        // 比较前一个值，将比较大的值存入            if(op < pist){                  op = pist;            }        }        return op;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def maxProfit(self, prices: List[int]) -> int:        min = prices[0]; # 预设索引0        op = 0;                # 从索引1开始练遍历        for i in range(1,len(prices)):                        # 找出最小值            if prices[i] < min :                min = prices[i]                        # 把两值的相差存入            elif((prices[i] - min) > op): # 比较原本的 op                op = prices[i] - min # 将比较大的值存入                return op;

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/04/18/LeetCode-121-Best-Time-to-Buy-and-Sell-Stock-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论