بهترین زمان خرید و فروش سهام
Best Time to Buy/Sell Stocksدر نسخه یک‌تراکنشی Stock، یک بار Array را پیمایش می‌کنیم، کمترین قیمت دیده‌شده را نگه می‌داریم و سود فروش در قیمت فعلی را با best profit مقایسه می‌کنیم.
اول این مفهوم را در ذهن نگه دار
در نسخه یک‌تراکنشی Stock، یک بار Array را پیمایش می‌کنیم، کمترین قیمت دیده‌شده را نگه می‌داریم و سود فروش در قیمت فعلی را با best profit مقایسه می‌کنیم.
چطور کار می‌کند؟ ساده و مرحله‌ای
خرید باید قبل از فروش باشد، پس فقط minimumهای قبلی candidate خرید هستند.
یک pass زمان O(n) و حافظه O(1) می‌دهد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
constraint و edge case را بازگو کن.
pattern و invariant را پیدا کن.
قبل از کد یک مثال کوچک را دستی اجرا کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای بهترین زمان خرید و فروش سهام هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function maxProfit(prices) {
let minPrice = Infinity;
let best = 0;
for (const price of prices) {
minPrice = Math.min(minPrice, price);
best = Math.max(best, price - minPrice);
}
return best;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی invariant pattern با constraint مسئله هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- قبل از تعریف invariant مستقیم سراغ کد نرو.
- قبل از جواب صحیح ساده، زود optimization نکن.
مدل یک پاسخ حرفه‌ای
قیمت‌ها را sort نکن چون ترتیب زمانی را از بین می‌برد؛ minimum تاریخی را نگه دار.
بهترین زمان خرید و فروش سهام چه مسئله‌ای را حل می‌کند؟
در نسخه یک‌تراکنشی Stock، یک بار Array را پیمایش می‌کنیم، کمترین قیمت دیده‌شده را نگه می‌داریم و سود فروش در قیمت فعلی را با best profit مقایسه می‌کنیم.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
قبل از تعریف invariant مستقیم سراغ کد نرو.