LeetCode Note Java 00121：Best Time to Buy and Sell Stock

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 449 所需閱讀時間 ≈ 2 分鐘

回傳最高收益。

題目

Best Time to Buy and Sell Stock Easy

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.

我的解法

想法

計算每個 price 買進後可能的最高收益來更新最佳收益：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        int maxP = 0;
        for (int i = 0; i < prices.length - 1; i++) { // 買進的價位
            for (int j = i + 1; j < prices.length; j++) { // 賣出的價位
                int diff = prices[j] - prices[i];
                if (diff > maxP) {
                    maxP = diff;
                }
            }
        }
        return maxP;
    }
}

O(n*n) 最暴力的雙層迴圈果然超時了。

想法 2

只能跑一圈的話就必須好好設計變數，記錄當前可能的最低買進價錢跟最高收益。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, maxP = 0;
        for (int price : prices) {
          min = price < min ? price : min; // 更新 最低買進價位
          int profit = price - min; // 計算 當次收益
          maxP = profit > maxP ? profit : maxP; // 更新 最高收益
        }
        return maxP;
    }
}

重點

  • 最後的 最高收益 不一定是由最後的 最低買進價位 得出。

重點物件或方法

  • Integer.MAX_VALUE

檢討

網路上有著各式方法，只好見一套學一套。

Sliding Window：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        int left = 0; // 買進位置
        int right = 1; // 賣出位置
        int maxProfit = 0;
        while (right < prices.length) {
            if (prices[left] < prices[right]) {
                maxProfit = Math.max(maxProfit, prices[right] - prices[left]);
                right++;
            } else {
                left = right;
                right++;
            }
        }
        return maxProfit;
    }
}

重點：

  • 其實概念跟前面的 想法 2 一樣，只是寫法不同。

  • Sliding Window 是這種解題技巧的名稱，可以減少暴力法中的重複計算。

參考資料

neetcode-gh/leetcode/blob/main/java/121-Best-Time-to-Buy-and-Sell-Stock.java

演算法筆記系列 — Two Pointer 與Sliding Window

Leetcode 刷題 pattern - Sliding Window