เมื่อไรจะซื้อ/ขายหุ้น? อาร์เรย์ที่กำหนดประกอบด้วยราคารายวันสำหรับหุ้น พยายามหากำไรสูงสุด

Input: [20,10,30,44,26,40,50]
Output: 58
Explanation: 
Buy on day 2 and sell on day 4, profit = 44-10 = 34.
Buy on day 5 and sell on day 7, profit = 50-26 = 24.

กระบวนการคิด:

จากคำถามก่อนหน้า Move Zeros เรารู้ว่าอย่างน้อยเราต้องการวนซ้ำอาร์เรย์อินพุตหนึ่งครั้ง ดังนั้นความซับซ้อนของเวลาจะเป็น O(n) เราสามารถใช้โครงสร้างข้อมูลเพิ่มเติม (เช่น Array/Linked List/Map/Set) เพื่อช่วยเราจัดเก็บกำไรแบบวันต่อวัน และรวมกำไรไว้ตอนท้าย แต่เดี๋ยวก่อน เราสนใจจริงๆ ว่าวันไหนเราจะทำกำไรได้เท่าไหร่? หรือเราสามารถสรุปกำไรทั้งหมดในขณะที่วนลูปผ่านอาร์เรย์อินพุตได้หรือไม่?

สารละลาย:

makeProfit(prices) {
    // Use a constant space O(1) to record total profit.
    let profit = 0;
    // While looping through the input array, we calculate the profit and add it to the sum.
    for(let i = 0; i < prices.length - 1; i++) {
        profit += Math.max(0, prices[i + 1] - prices[i]);
    }
    return profit;
};

หมายเหตุสำคัญ:

  1. ประหยัดพื้นที่
  2. จะติดตามและคำนวณกำไรจากอาร์เรย์อินพุตได้อย่างไร

คำถามต่อไปคืออะไร?

ค้นหารายการที่ซ้ำกัน — เมื่อระบุอาร์เรย์ของตัวเลข ให้คืนค่าเป็นจริงหากตัวเลขใดๆ ปรากฏมากกว่าหนึ่งครั้งในอาร์เรย์ หรือส่งคืนค่าเท็จ (<<กระบวนการคิดและแนวทางแก้ไข»)

ก่อนที่คุณจะไป -

ไม่มีวิธีใดที่จะดีไปกว่าการสนับสนุนฉันมากกว่าการติดตามฉันบนสื่อ (Victor Lin) บอกเลยว่าควรเขียนเพิ่ม!

คุณรู้ไหมว่าคุณสามารถให้มากถึง 50 👏's โดยการกดปุ่ม 👏? ลองดูสิถ้าคุณ reeeeeeallyชอบบทความนี้!