جمع‌آوری آب باران
Rain Terraces / Trapping Rain WaterTrapping Rain Water مقدار آبی را می‌خواهد که بین ستون‌ها جمع می‌شود. ارتفاع آب روی index i به کمینه بلندترین ستون چپ و راست آن محدود است.
اول این مفهوم را در ذهن نگه دار
Trapping Rain Water مقدار آبی را می‌خواهد که بین ستون‌ها جمع می‌شود. ارتفاع آب روی index i به کمینه بلندترین ستون چپ و راست آن محدود است.
چطور کار می‌کند؟ ساده و مرحله‌ای
در روش Two Pointer، leftMax و rightMax را نگه می‌داریم و سمتی را حرکت می‌دهیم که boundary کوچک‌تری دارد.
این روش O(n) زمان و O(1) حافظه می‌خواهد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
constraint و edge case را بازگو کن.
pattern و invariant را پیدا کن.
قبل از کد یک مثال کوچک را دستی اجرا کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای جمع‌آوری آب باران هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function trap(height) {
let l = 0, r = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;
while (l < r) {
if (height[l] <= height[r]) {
leftMax = Math.max(leftMax, height[l]);
water += leftMax - height[l++];
} else {
rightMax = Math.max(rightMax, height[r]);
water += rightMax - height[r--];
}
}
return water;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی invariant pattern با constraint مسئله هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- قبل از تعریف invariant مستقیم سراغ کد نرو.
- قبل از جواب صحیح ساده، زود optimization نکن.
مدل یک پاسخ حرفه‌ای
توضیح بده چرا حرکت دادن boundary کوچک‌تر درست است: همان سمت کوچک‌تر همین حالا سقف water level موقعیت فعلی را تعیین کرده است.
جمع‌آوری آب باران چه مسئله‌ای را حل می‌کند؟
Trapping Rain Water مقدار آبی را می‌خواهد که بین ستون‌ها جمع می‌شود. ارتفاع آب روی index i به کمینه بلندترین ستون چپ و راست آن محدود است.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
قبل از تعریف invariant مستقیم سراغ کد نرو.