Լոգարիթմական պատուհանի առավելագույն LeetCode լուծում


Հաճախակի հարցնում են Adobe Amazon Ամերիքան Էքսպրես քարտ խնձոր ByteDance Միջնաբերդ Google Intel LinkedIn Մաթեմատիկական աշխատանքներ Microsoft Պատգամախոս PayPal Quora Salesforce Splunk Tesla Twilio ծլվլոց Երկու սիգմա Uber VMware Հաչոց
Bookin.com Կատեգորիաներ - Դժվար Cruise Automatiin instacart tiktokԴիտումներ 6

Խնդիրի հայտարարություն

Լոգարիթմական պատուհանի առավելագույն LeetCode լուծումն ասում է, որ ձեզ տրված է ամբողջ թվերի զանգված nums, և կա չափի լոգարիթմական պատուհան k որը շարժվում է զանգվածի հենց ձախից դեպի աջ։ Դուք կարող եք տեսնել միայն k թվերը պատուհանում: Ամեն անգամ, երբ լոգարիթմական պատուհանը շարժվում է ուղիղ մեկ դիրքով:

Վերադառնալ առավելագույն լոգարիթմական պատուհան.

Օրինակ 1:

Մուտք:

 nums = [1,3,-1,-3,5,3,6,7], k = 3

Արդյունք:

 [3,3,5,5,6,7]

Բացատրությունը.

 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7

3

 1 [3  -1  -3] 5  3  6  7

3

 1  3 [-1  -3  5] 3  6  7

5

 1  3  -1 [-3  5  3] 6  7

5

 1  3  -1  -3 [5  3  6] 7

6

 1  3  -1  -3  5 [3  6  7]

7

Օրինակ 2:

Մուտք:

 nums = [1], k = 1

Արդյունք:

 [1]

Սահմանափակումներ.

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

ԱԼԳՈՐԻԹՄ –

ԳԱՂԱՓԱՐ –

    • Լոգարիթմական պատուհանի առավելագույնը գտնելու համար: Նախ, մենք կկենտրոնանանք Տրված միջակայքի վրա, այսինքն՝ K-ի և առավելագույն տարրը գտնվում է այդ տիրույթում: Հիմնականում այն, ինչ մենք կանենք, կազմում է մեկ Deque and Answer ցուցակ, որը վերադարձնում է պատասխանը:
    • Այնուհետև կանցնի զանգվածի միջով և կստուգի այն պայմանը, որ դեկի վերին մասը փոքր է ընթացիկ արժեքից, այնուհետև տարրը դուրս կբերի հերթից, այլապես տարրի ինդեքսը մղեք դեկ:
    • Այնուհետև մենք նորից կստուգենք երկու պայման, եթե առավելագույն տարրը չի գտնվում տիրույթի սահմաններում, եթե այն չի ընկած, ապա այն դուրս կբերենք դեկից և ևս մեկ պայման, այսինքն, եթե ինդեքսը մեծ է կամ հավասար է K-1-ին, ապա մենք սկսեք լրացնել մեր պատասխանների ցուցակը և դրան կցեք առաջին տարրի հերթը և վերջապես վերադարձրեք պատասխանը:

ՄՈՏԵՑՈՒՄ –

  • Սկզբում մենք կստեղծենք մեկ Deque և մեկ պատասխան ցուցակ և վերջում կվերադարձնենք պատասխանը:
  • Դրանից հետո մենք կանցնենք ամբողջ զանգվածով, և while պայմանի օգնությամբ կստուգենք, արդյոք q[-1] < ընթացիկ val, եթե այս պայմանը բավարարում է, ապա վերջին տարրը դուրս կգա q-ից: Հակառակ դեպքում տարրի ինդեքսը մղեք q-ի մեջ:
  • Այնուհետև մենք կստուգենք՝ առավելագույն տարրը գտնվում է տիրույթում, թե ոչ՝ օգտագործելով ինդեքսը – K == q[0]: եթե պայմանը բավարարում է, ապա տարրը կթափվի q-ից՝ օգտագործելով q.popleft():
  • Կրկին ստուգեք, արդյոք ինդեքսը հավասար է K-1-ին կամ ավելի մեծ, քան K-1-ը, ապա պարզապես ավելացրեք առավելագույն տարրը պատասխանների ցանկում և վերադարձրեք պատասխանը:
  • Այսպիսով, մենք կգտնենք Sliding Window Maximum-ը:

ԼՈՒԾՄԱՆ ՊԱՏԿԵՐ –

Լոգարիթմական պատուհանի առավելագույն LeetCode լուծումPin Լոգարիթմական պատուհանի առավելագույն LeetCode լուծումPin Լոգարիթմական պատուհանի առավելագույն LeetCode լուծումPin Լոգարիթմական պատուհանի առավելագույն LeetCode լուծումPin

 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        
        for i,v in enumerate(nums):
            
              while(q and nums[q[-1]] <= v):
                    q.pop()
              
              q.append(i)
                
              
              if q[0] == i-k:
                    q.popleft()
              
            
              if i >= k-1:
                    ans.append(nums[q[0]])
        return ans
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return nums;
        }
        int[] ans = new int[n - k + 1];
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) {
                q.pollLast();
            }
            q.offer(i);
            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[q.peek()];
            }
        }
        return ans;
    }
}

Timeամանակի բարդությունO(N), Քանի որ մենք ամբողջ զանգվածն անցել ենք միայն մեկ անգամ:

Տիեզերական բարդությունO(N), քանի որ մենք ստեղծել ենք մեկ Deque:

ՆՄԱՆ ՀԱՐՑԵՐ – https://www.tutorialcup.com/interview/algorithm/sliding-window-technique.htm

Լոգարիթմական պատուհանի առավելագույն հարցազրույցի հարցերը

Translate »