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

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

Լոգարիթմական պատուհանի առավելագույն 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 <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 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-ը:

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

Pin Pin Pin 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

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