မှတ်ချက် – ဒီ Post သည် Algorithm Interview Preparation အပိုင်းဆက်ဖြစ်သည်။

ကျနော်တို့ဒီနေ့ရှင်းမယ့် ပြဿနာက 739. Daily Temperatures ဆိုတဲ့ leetcode question ဘဲဖြစ်ပါတယ်။

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

 

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]
 

Constraints:

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

မေးခွန်းက temperatures ဆိုတဲ့ daily temperature ဖြစ်တဲ့ array တခုပေးထားမယ်။ သူလိုချင်တာက လက်ရှိထက်ပိုပူတဲ့အပူချိန်ရောက်ဖို့ ဘယ်လောက်စောင့်ရမလဲဆိုတာ၊ တကယ်လို့ နောက်ရက်တွေမရှိတော့ဘူးဆို 0 ထားလိုက်တဲ့။

ဥပမာတခုကိုအရင်ကြည့်လိုက်ရအောင်

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

[73,74,75,71,69,72,76,73]
[1 , 1, 4, 2, 1, 1, 0, 0]

သူပေးထားတဲ့ temperatures တွေထဲမှာ 73 ဖြစ်တဲ့ရက်နောက်နေ့မှာ 74 ဆိုတော့ပိုပူတယ်။ အဲ့တော့ 1 ရက်အတွင်းဖြစ်တဲ့အတွက် 1။ အပူချိန် 75 ဖြစ်တဲ့ရက်ကိုကြည့်လိုက်တဲ့အချိန်မှာ 76 ရောက်တဲ့နေ့ထိဆို 4 ရက်ကြာတယ်။ 71 ဖြစ်တဲ့ရက်ဆိုပိုပူတဲ့ရက်ရဖို့ 2 ရက်ကြာတယ်။ နောက်ဆုံး 76 နဲ့ 73 ကြတော့သူ့ထက်ပိုပူတဲ့ရက်မရှိတော့တဲ့အတွက် 0။ ဒီလောက်ဆိုမေးခွန်းကိုနားလည်ပီထင်ပါတယ်။

အဖြေကိုမကြည့်ခင် ကိုယ်ပိုင်ဖြေကြည့်ဖို့ တိုက်တွန်းလိုပါတယ်။ အောက်မှာအဖြေနှင့် ရှင်းလင်းချက်ကိုဖော်ပြထားပါတယ်။

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    let result = new Array(temperatures.length).fill(0);

    let stack = [];

    for(let i=0; i < temperatures.length; i++) {
        while(stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const index = stack.pop()
            result[index] = i - index;
        }

        stack.push(i)
    }

    return result;
};

ဒီအဖြေကိုမရှင်းပြခင် ဒီမှာ O(n^2) နှင့်လဲဖြေရှင်းလို့ရပါတယ်။ ကျနော်စမ်းပီး submit လုပ်တာတော့ time exceed ဖြစ်သွားတယ်။

ပထမဆုံး result ဆိုပီးတော့ array တခုတည်ဆောက်လိုက်တယ်။ သူ့ရဲ့ default value က 0 ဖြစ်ပီးတော့ temperatures ရှိတဲ့ length အတိုင်းဘဲတည်ဆောက်လိုက်ပါတယ်။ ဘာလို့လဲဆို ကျနော်တို့က temperatures ရှိတဲ့ရက်အတိုင်းပြန်ဖော်ပြရမှာမလို့ပါ။

နောက် stack ကြေငြာလိုက်တယ်။ temperatures ကို loop ပတ်ပီးတော့ လက်ရှိ index ကို stack ထဲထည့်လိုက်တယ်။ အဲ့ stack ပေါ်မူတည်ပီးတော့ temperatures ကွာတဲ့ index ကိုရှာပီး result ထဲထည့်လိုက်တယ်။ နောက်ဆုံး result ကို return ပြန်ပေးလိုက်တယ်။

အဖြေကလွယ်လွယ်ရှင်းရှင်းလေး ဒါပေမယ့်တခါတလေကြရင် stack ဖြစ်နေတက်တယ်၊ တခုချင်းစီဘယ်လိုအလုပ်လုပ်သွားလဲသိချင်တယ်ဆိုရင် debugger နဲ့တခုချင်းစီ inspect လုပ်ပီးကြည့်ကြည့်စေချင်ပါတယ်။

Time/Space Complexity က O(n)