題目

思路

遍歷三次，維護兩個數組：

• 第一次從前向后遍歷，生成“左邊最小”數組
• 第二次從后向前遍歷，生成“右邊最大”數組
• 第三次從前向后遍歷，用“右邊最大”數組減去“左邊最小”數組，找出最大值

例如，prices = {7, 1, 5, 3, 6, 4};

左邊最小 [7, 1, 1, 1, 1, 1] 右邊最大 [7, 6, 6, 6, 6, 4] 差值 [0, 5, 5, 5, 5, 3] 故最大差值為：5

另外，注意添加輸入空數組的判斷，避免越界異常。

題解

class Solution {// O(n) 復雜度public int maxProfit(int[] prices) {// 空值校驗if (prices.length == 0) return 0;int len = prices.length;int leftMinArr[] = new int[len];// 輔助數組：左邊的最小數int rightMaxArr[] = new int[len];// 輔助數組：右邊的最大數leftMinArr[0] = prices[0];rightMaxArr[len - 1] = prices[len - 1];//左邊最小for (int i = 1; i < len; i++) {if (prices[i] < leftMinArr[i - 1]) {leftMinArr[i] = prices[i];} else {leftMinArr[i] = leftMinArr[i - 1];}}//右邊最大for (int i = len - 2; i >= 0; i--) {if (prices[i] > rightMaxArr[i + 1]) {rightMaxArr[i] = prices[i];} else {rightMaxArr[i] = rightMaxArr[i + 1];}}//最大差值int max = 0;for (int i = 0; i < len; i++) {int diff = rightMaxArr[i] - leftMinArr[i];if (max < diff) {max = diff;}} // System.out.println(Arrays.toString(leftMinArr)); // System.out.println(Arrays.toString(rightMaxArr));return max;}//測試用例public static void main(String[] args) {Solution solution = new Solution();int[] prices = {7, 1, 5, 3, 6, 4};int res = solution.maxProfit(prices);System.out.println(res);}}

附：在評論區看到的最優解

從前向后遍歷一次
記錄當前遇到的最小值和最大值
注意 最大值應該在最小值之后， 因此 若最小值更新了就把最大值也更新成與之相同
每次得出最大值和最小值的時候就和max比較取最大

C語言：

int maxProfit(int* prices, int pricesSize){if(pricesSize==0) return 0;int result=0,max=prices[0],min=prices[0];for(int i=1;i<pricesSize;i++){if(prices[i]>max) //股票價格上升了{max=prices[i];result=fmax(max-min,result);}else if(prices[i]<min) //最低價格下降了{min=max=prices[i];}}return result; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的leetcode 121. 买卖股票的最佳时机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。