home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Subarray ต่อเนื่องยาวที่สุดที่ Absolute Diff ≤ Limit ใน C++

สมมติว่าเรามีอาร์เรย์ nums และ limit หาขนาด subarray ยาวที่สุดที่ความต่างสัมบูรณ์ระหว่างสมาชิกใดๆ ≤ limit

ตัวอย่าง: nums = [8,2,4,7], limit = 4 ผลลัพธ์ = 2 (subarray [2,4] หรือ [4,7])

วิธีแก้ปัญหา (Sliding Window + Deque)

  1. ใช้ deque สองตัว: maxD (descending) และ minD (ascending)
  2. ขยาย window ด้วย i:
    • maintain maxD, minD ให้เรียงถูกต้อง
    • ถ้า maxD.front() - minD.front() > limit: ย่อ window จาก j
  3. อัปเดตความยาวสูงสุด
  4. เวลา O(n)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int longestSubarray(vector<int>& nums, int k) { 
        int ret = 0, j = 0; 
        deque<int> maxD, minD; 
        int n = nums.size(); 
        for (int i = 0; i < n; i++) { 
            while (!maxD.empty() && maxD.back() < nums[i]) maxD.pop_back(); 
            while (!minD.empty() && minD.back() > nums[i]) minD.pop_back(); 
            maxD.push_back(nums[i]); 
            minD.push_back(nums[i]); 
            while (maxD.front() - minD.front() > k) { 
                if (nums[j] == maxD.front()) maxD.pop_front(); 
                if (nums[j] == minD.front()) minD.pop_front(); 
                j++; 
            } 
            ret = max(ret, i - j + 1); 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {7,8,2,4}; 
    cout << (ob.longestSubarray(v, 4)); 
}

ข้อมูลนำเข้า

{7,8,2,4}, 4

ผลลัพธ์

2