ဆိုင်တစ်ခု Leetcode ဖြေရှင်းချက်အတွက်အထူးလျှော့စျေးနှင့်အတူနောက်ဆုံးစျေးနှုန်းများ


ခက်ခဲအဆင့် လွယ်ကူသော
အခင်းအကျင်း Dream11

အဆိုပါပြproblemနာကိုစျေး Leetcode ဖြေရှင်းချက်အတွက်အထူးလျှော့စျေးနှင့်အတူနောက်ဆုံးစျေးနှုန်းများကိုသင်ကသင့်အားပေးသည်ဟုဆိုသည် အခင်းအကျင်း စျေးနှုန်း၏။ ထုတ်ကုန်တစ်ခုစီအတွက်အထူးလျှော့စျေးရရှိသည်ဟုပြောသည့်အထူးအခြေအနေရှိသည်။ သင်ပေးထားသောခင်းကျင်းချက်ရှိ jth index တွင်ညီမျှသောပမာဏ၏လျှော့စျေးရရှိသည်။ ပေးထားသောခင်းကျင်းသည်ဆိုပါစို့ စျေးနှုန်းများ။ ဒါကြောင့် j ကနိမ့်ဆုံးအညွှန်းကိန်းဖြစ်လျှင် j> = i နှင့်စျေးနှုန်း [j] <= စျေးနှုန်း [i] ဆိုပါကစျေးနှုန်း [i] အတွက်စျေးနှုန်းလျှော့စျေးရရှိမည်။ သို့သော်ဖြေရှင်းချက်ကိုရှေ့ဆက်မသွားမီဥပမာအနည်းငယ်ကြည့်ကြစို့။

ဆိုင်တစ်ခု Leetcode ဖြေရှင်းချက်အတွက်အထူးလျှော့စျေးနှင့်အတူနောက်ဆုံးစျေးနှုန်းများ

[8,4,6,2,3]
[4,2,4,2,3]

ရှင်းလင်းချက်။ ညာဘက်ရှိပထမဆုံးဒြပ်စင်သည်သူနှင့်ညီသည်သို့မဟုတ်ညီမျှသည် ၄ ​​ဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် ၄ ​​ကို ၈ ကိုနှုတ်လိုက်တယ်။ အလားတူပဲကျန်တဲ့ element တစ်ခုချင်းစီအတွက်လည်းတူညီတဲ့လုပ်ဆောင်မှုကိုလုပ်ဆောင်တယ်။

ဆိုင် Leetcode ဖြေရှင်းနည်းတွင်အထူးလျှော့စျေးဖြင့်နောက်ဆုံးစျေးနှုန်းအတွက်ချဉ်းကပ်မှု

ပြetနာတစ်ခု Leetcode Solution သည်အထူးလျှော့စျေးဖြင့်နောက်ဆုံးစျေးနှုန်းများသည်ရိုးရှင်းပါသည်။ ဘာလို့လဲဆိုတော့ဒါကပုံမှန်ဘ ၀ နဲ့ပုံမှန်ပြproblemနာအတွက်အနည်းငယ်ပြုပြင်ပြောင်းလဲမှုတစ်ခုဆိုတာကိုသတိပြုမိရင်ပေါ့။ အဆိုပါပြproblemနာကို stack သို့မဟုတ်တန်းစီသုံးပြီးဖြေရှင်းသောနောက်ထပ်သေးငယ်တဲ့ဒြပ်စင်၏အနည်းငယ်ပြုပြင်မွမ်းမံသည်။ ဒီတော့ဒီပြinနာမှာနောက် element သေးသေးလေးဒါမှမဟုတ်ညီမျှတဲ့ element ကိုရှာဖို့ကျွန်တော်တို့သုံးမယ်။

ဒီတော့ပြsolveနာကိုဖြေရှင်းဖို့၊ ငါတို့ကပုံတစ်ပုံကိုဖန်တီးလိုက်တယ်။ ပြီးတော့ကျွန်တော်တို့ကညွှန်းကိန်းတွေကို stack ကိုတွန်းတယ်။ အစပိုင်းမှာတော့ 0 ကို stack ထဲကိုထည့်လိုက်တယ်။ ယခုကျွန်ုပ်တို့သည် array အတွင်းရှိ element များကိုဖြတ်သန်းသွားသည်။ လက်ရှိဒြပ်စင်သည် s.top () အညွှန်းကိန်းတွင်ရှိသောဒြပ်စင်နှင့်ညီမျှမလားစစ်ဆေးသည်။ အကယ်၍ လက်ရှိဒြပ်စင်သည်ယခင်အခြေအနေကိုကျေနပ်ပါကကျွန်ုပ်တို့သည် element ကို pop နှင့် current တန်ဖိုးဖြင့်ထို index တွင်ရှိသောတန်ဖိုးကိုလျှော့ချပါမည်။ ယခုလက်ရှိအညွှန်းကိုတွန်း။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်နောက်ထပ်သေးငယ်သောသို့မဟုတ်တူညီသောဒြပ်စင်ကိုတွေ့ရှိနိုင်သည်။

ဆိုင် Leetcode ဖြေရှင်းနည်းတွင်အထူးလျှော့စျေးဖြင့်နောက်ဆုံးစျေးနှုန်းအတွက်ကုဒ်နံပါတ်

C ++ ကုဒ်

#include <bits/stdc++.h>
using namespace std;

vector<int> finalPrices(vector<int>& prices) {
    stack<int> s;
    s.push(0);
    for(int i=1;i<prices.size();i++){
        while(!s.empty() && prices[s.top()] >= prices[i])prices[s.top()] -= prices[i], s.pop();
        s.push(i);
    }
    return prices;
}

int main() {
    vector<int> prices = {8,4,6,2,3};
    vector<int> output = finalPrices(prices);
    for(int i=0;i<output.size();i++)
        cout<<output[i]<<" ";
}
4 2 4 2 3

ဂျာဗားကုဒ်

import java.util.*;
import java.io.*;

class Main {
    public static int[] finalPrices(int[] prices) {
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < prices.length; i++) {
            while (!s.isEmpty() && prices[s.peek()] >= prices[i])
                prices[s.pop()] -= prices[i];
            s.push(i);
        }
        return prices;
    }

    public static void main(String[] args) {
        int[] prices = {8,4,6,2,3};
        int[] output = finalPrices(prices);
        for(int i=0;i<output.length;i++)
            System.out.print(output[i]+" ");
    }
}
4 2 4 2 3

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ကျနော်တို့ input ကိုအပေါငျးတို့သဒြပ်စင်ဖြတ်သန်းကတည်းက။

အာကာသရှုပ်ထွေးမှု

အို (N)၊  ကျနော်တို့နောက်ထပ်အာကာသကိုအသုံးပြုတဲ့ stack ကိုအသုံးပြုပါ။