เมื่อไรจะซื้อ/ขายหุ้น? อาร์เรย์ที่กำหนดประกอบด้วยราคารายวันสำหรับหุ้น พยายามหากำไรสูงสุด
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; };
หมายเหตุสำคัญ:
- ประหยัดพื้นที่
- จะติดตามและคำนวณกำไรจากอาร์เรย์อินพุตได้อย่างไร
คำถามต่อไปคืออะไร?
ค้นหารายการที่ซ้ำกัน — เมื่อระบุอาร์เรย์ของตัวเลข ให้คืนค่าเป็นจริงหากตัวเลขใดๆ ปรากฏมากกว่าหนึ่งครั้งในอาร์เรย์ หรือส่งคืนค่าเท็จ (<<กระบวนการคิดและแนวทางแก้ไข»)
ก่อนที่คุณจะไป -
ไม่มีวิธีใดที่จะดีไปกว่าการสนับสนุนฉันมากกว่าการติดตามฉันบนสื่อ (Victor Lin) บอกเลยว่าควรเขียนเพิ่ม!
คุณรู้ไหมว่าคุณสามารถให้มากถึง 50 👏's โดยการกดปุ่ม 👏? ลองดูสิถ้าคุณ reeeeeeallyชอบบทความนี้!