ተንሸራታች መስኮት ከፍተኛው የ LeetCode መፍትሄ


ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን አሜሪካን ኤክስፕረስ ፓም ByteDance ግልብጥብጥ google Intel LinkedIn የሂሳብ ስራዎች የ Microsoft በ Oracle የ PayPal Quora Salesforce Splunk tesla ቴሊዮ ትዊተር ሁለት ሲግማ በ Uber VMware Yelp
Bookin.com ምድቦች - ከባድ የሽርሽር Automatiin instacart tiktokዕይታዎች 33

የችግሩ መግለጫ

ተንሸራታች መስኮት ከፍተኛው የ 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

አልጎሪዝም -

IDEA -

    • ተንሸራታች መስኮት ከፍተኛውን ለማግኘት። በመጀመሪያ፣ በተሰጠው ክልል ማለትም K ላይ እናተኩራለን እና በዚህ ክልል ውስጥ ያለው ከፍተኛው ንጥረ ነገር አለ። በመሠረቱ እኛ የምናደርገው መልሱን የሚመልስ አንድ Deque እና Answer ዝርዝር ማድረግ ነው።
    • ከዚያም በድርድር ውስጥ ያልፋል እና የዴኬው የላይኛው ክፍል ከአሁኑ እሴት ያነሰ ከሆነ ሁኔታውን ይፈትሹ ከዚያም ኤለመንቱን ከወረፋው ላይ ያውጡ እና የኤለመንቱን መረጃ ጠቋሚ ወደ deque ይግፉት።
    • ከዚያ እንደገና ሁለት ሁኔታዎችን እንፈትሻለን ከፍተኛው ኤለመንት በክልል ውስጥ የማይዋሽ ከሆነ የማይዋሽ ከሆነ ከዲኪው ውስጥ ያውጡት እና አንድ ተጨማሪ ሁኔታ ማለትም መረጃ ጠቋሚው ከ K-1 የበለጠ ወይም እኩል ከሆነ ከዚያ እኛ እናደርጋለን የመልሶቻችንን ዝርዝር መሙላት ይጀምሩ እና የመጀመሪያውን ኤለመንት ወደ እሱ ያስገቡ እና በመጨረሻ መልሱን ይመልሱ።

አቀራረብ -

  • በመጀመሪያ አንድ Deque እና አንድ መልስ ዝርዝር እንፈጥራለን እና በመጨረሻም መልሱን እንመልሳለን.
  • ከዚያ በኋላ፣ መላውን አደራደር እናልፋለን፣ እና በሁኔታው እገዛ፣ q[-1] < current val ይህ ሁኔታ የሚያሟላ ከሆነ የመጨረሻውን ንጥረ ነገር ከq እንደሚወጣ እናረጋግጣለን። ያለበለዚያ የንጥል መረጃ ጠቋሚውን ወደ q.
  • ከዚያም ከፍተኛው ኤለመንት በክልል ውስጥ መኖሩን ወይም አለመሆኑን በመረጃ ጠቋሚ - K == q[0] እንፈትሻለን። ሁኔታው ካረካ q.popleft() በመጠቀም ኤለመንቱን ከq ይወጣል።
  • ኢንዴክስ ከK-1 ጋር እኩል መሆኑን ወይም ከK-1 በላይ መሆኑን በድጋሚ አረጋግጥ ከዚያም በቀላሉ ከፍተኛውን አካል ወደ መልስ ዝርዝር ውስጥ ጨምረው መልሱን ይመልሱ።
  • ስለዚህ ተንሸራታች መስኮት ከፍተኛውን እናገኛለን።

የመፍትሄው ምስል -

ተንሸራታች መስኮት ከፍተኛው የ LeetCode መፍትሄጭንቅላታም መያያዣ መርፌ ተንሸራታች መስኮት ከፍተኛው የ LeetCode መፍትሄጭንቅላታም መያያዣ መርፌ ተንሸራታች መስኮት ከፍተኛው የ LeetCode መፍትሄጭንቅላታም መያያዣ መርፌ ተንሸራታች መስኮት ከፍተኛው የ LeetCode መፍትሄጭንቅላታም መያያዣ መርፌ

 

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;
    }
}

የጊዜ ውስብስብነት: ኦ(N)፣ መላውን ድርድር አንድ ጊዜ እንዳሻገርነው።

የቦታ ውስብስብነትአንድ Deque እንደፈጠርነው ኦ(N)።

ተመሳሳይ ጥያቄዎች - https://www.tutorialcup.com/interview/algorithm/sliding-window-technique.htm

ከፍተኛ ተንሸራታች-መስኮት-maxi ቃለ መጠይቅ ጥያቄዎች

Translate »