راه حل حداکثر LeetCode پنجره کشویی


اغلب در خشت آمازون امریکن اکسپرس سیب ByteDance دژ گوگل اینتل لینک کارهای ریاضی مایکروسافت وحی پی پال Quora Salesforce پاره شدن تسلا Twilio توییتر دو سیگما حال بارگذاری آموزش VMware Yelp
Bookin.com دسته ها - سخت کروز اتوماتیین instacart تاکسینمایش ها 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

الگوریتم -

اندیشه -

    • به منظور یافتن حداکثر پنجره کشویی. اول، ما بر روی محدوده داده شده یعنی K تمرکز خواهیم کرد و عنصر حداکثر در آن محدوده قرار دارد. اساساً کاری که ما انجام خواهیم داد این است که یک لیست Deque and Answer ایجاد کنیم که پاسخ را برمی گرداند.
    • سپس از طریق آرایه عبور می کند و شرایط را بررسی می کند که بالای deque کمتر از مقدار فعلی باشد، سپس عنصر را از صف خارج می کند، در غیر این صورت شاخص عنصر را به داخل deque فشار دهید.
    • سپس دوباره دو شرط را بررسی می کنیم اگر عنصر ماکزیمم در محدوده قرار نگیرد، اگر قرار نگیرد، آن را از deque خارج می کنیم و یک شرط دیگر یعنی اگر شاخص بزرگتر یا مساوی K-1 باشد، آن را بررسی می کنیم. شروع به پر کردن لیست پاسخ های خود کنید و dequeue از اولین عنصر را به آن اضافه کنید و در آخر پاسخ را برگردانید.

رویکرد -

  • ابتدا یک Deque و یک لیست پاسخ ایجاد می کنیم و در آخر پاسخ را برمی گردانیم.
  • پس از آن کل آرایه را پیمایش می کنیم و با کمک شرط while بررسی می کنیم که اگر این شرط وجود داشته باشد 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;
    }
}

پیچیدگی زمان: O(N)، همانطور که کل آرایه را فقط یک بار پیمایش کرده ایم.

پیچیدگی فضا: O(N)، همانطور که یک Deque ایجاد کرده ایم.

سوالات مشابه - https://www.tutorialcup.com/interview/algorithm/sliding-window-technique.htm

سوالات مصاحبه ماکسی کشویی

Translate »