หน้าต่างบานเลื่อนสูงสุด LeetCode Solution

คำชี้แจงปัญหา

โซลูชัน LeetCode สูงสุดของหน้าต่างบานเลื่อนบอกว่า – คุณจะได้รับอาร์เรย์ของจำนวนเต็ม numsและมีหน้าต่างบานเลื่อนขนาด k ซึ่งเคลื่อนจากด้านซ้ายสุดของอาร์เรย์ไปทางขวาสุด คุณสามารถดูได้เพียง k ตัวเลขในหน้าต่าง แต่ละครั้งที่หน้าต่างบานเลื่อนเลื่อนไปทางขวาทีละตำแหน่ง

บริการรถส่ง หน้าต่างบานเลื่อนสูงสุด.

1 ตัวอย่าง:

Input:

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

Output:

 [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 ตัวอย่าง:

Input:

 nums = [1], k = 1

Output:

 [1]

ข้อ จำกัด :

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

อัลกอริทึม –

ความคิด -

• • เพื่อที่จะหาหน้าต่างบานเลื่อนสูงสุด อันดับแรก เราจะเน้นที่ช่วงที่กำหนด เช่น K และองค์ประกอบสูงสุดอยู่ภายในช่วงนั้น โดยพื้นฐานแล้วสิ่งที่เราจะทำคือสร้างรายการ Deque และ Answer หนึ่งรายการซึ่งส่งคืนคำตอบ
  • จากนั้นจะข้ามผ่านอาร์เรย์และตรวจสอบเงื่อนไขหากด้านบนของ deque น้อยกว่าค่าปัจจุบันจากนั้นดึงองค์ประกอบออกจากคิวมิฉะนั้นจะผลักดัชนีองค์ประกอบเข้าไปใน deque
  • จากนั้นอีกครั้ง เราจะตรวจสอบสองเงื่อนไขว่าองค์ประกอบสูงสุดไม่อยู่ภายในช่วงถ้ามันไม่โกหก จากนั้นให้ดึงออกจาก deque และอีกหนึ่งเงื่อนไขคือถ้าดัชนีมากกว่าหรือเท่ากับ K-1 เราจะ เริ่มกรอกรายการคำตอบของเราและเพิ่ม dequeue ขององค์ประกอบแรกลงในนั้นและที่คำตอบสุดท้าย

เข้าใกล้ -

• ในตอนแรก เราจะสร้าง Deque หนึ่งรายการและรายการคำตอบหนึ่งรายการ และสุดท้าย เราจะส่งคืนคำตอบ
• หลังจากนั้น เราจะสำรวจผ่านอาร์เรย์ทั้งหมด และด้วยความช่วยเหลือของเงื่อนไข while เราจะตรวจสอบว่า q[-1] < วาลปัจจุบัน หากเงื่อนไขนี้เป็นไปตามเงื่อนไข จะแสดงองค์ประกอบสุดท้ายจาก q ออกมาหรือไม่ อย่างอื่นผลักดัชนีองค์ประกอบเป็น q
• จากนั้นเราจะตรวจสอบว่าองค์ประกอบสูงสุดอยู่ภายในช่วงหรือไม่โดยใช้ดัชนี – K == q[0] หากเงื่อนไขเป็นไปตามเงื่อนไข จะทำให้องค์ประกอบปรากฏขึ้นจาก q โดยใช้ q.popleft()
• ตรวจสอบอีกครั้งว่าดัชนีมีค่าเท่ากับ K-1 หรือมากกว่า K-1 จากนั้นเพียงเพิ่มองค์ประกอบสูงสุดในรายการคำตอบและส่งคืนคำตอบ
• ดังนั้นเราจะพบหน้าต่างบานเลื่อนสูงสุด

ภาพของการแก้ปัญหา –

หมุด หมุด หมุด หมุด

 

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

คำถามสัมภาษณ์แบบเลื่อน-หน้าต่าง-แมกซี่ยอดนิยม