Computer >> Máy Tính >  >> Lập trình >> C ++

Dải con liên tục dài nhất với chênh lệch tuyệt đối nhỏ hơn hoặc bằng giới hạn trong C ++

Giả sử chúng ta có một mảng các số nguyên được gọi là num và một giới hạn số nguyên, chúng ta phải tìm kích thước của mảng con dài nhất không rỗng sao cho sự khác biệt tuyệt đối giữa hai mục bất kỳ của mảng con này nhỏ hơn hoặc bằng giới hạn đã cho.

Vì vậy, nếu đầu vào là nums =[8,2,4,7], limit =4, thì đầu ra sẽ là 2, điều này là do -

  • [8] vì vậy | 8-8 | =0 <=4.

  • [8,2] nên | 8-2 | =6> 4.

  • [8,2,4] nên | 8-2 | =6> 4.

  • [8,2,4,7] nên | 8-2 | =6> 4.

  • [2] so | 2-2 | =0 <=4.

  • [2,4] vì vậy | 2-4 | =2 <=4.

  • [2,4,7] nên | 2-7 | =5> 4.

  • [4] vì vậy | 4-4 | =0 <=4.

  • [4,7] vì vậy | 4-7 | =3 <=4.

  • [7] vì vậy | 7-7 | =0 <=4.

Cuối cùng, kích thước của mảng con dài nhất là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • ret:=0, i:=0, j:=0

  • Xác định một deque maxD và một deque minD khác

  • n:=kích thước của nums

  • để khởi tạo i:=0, khi i

    • while (not maxD trống và phần tử cuối cùng của maxD

      • xóa phần tử cuối cùng khỏi maxD

    • while (không phải minD trống và phần tử cuối cùng của minD> nums [i]), do -

      • xóa phần tử cuối cùng khỏi minD

    • chèn nums [i] vào cuối maxD

    • chèn nums [i] vào cuối minD

    • while (phần tử đầu tiên của maxD - phần tử đầu tiên của minD)> k, do -

      • nếu nums [j] giống với phần tử đầu tiên của maxD, thì−

        • xóa phần tử phía trước khỏi maxD

      • nếu nums [j] giống với phần tử đầu tiên của minD, thì -

        • xóa phần tử phía trước khỏi minD

      • (tăng j lên 1)

    • ret:=tối đa ret và (i - j + 1)

  • trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestSubarray(vector<int>& nums, int k) {
      int ret = 0;
      int i = 0;
      int j = 0;
      deque<int> maxD;
      deque<int> 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;
   }
};
main(){
   Solution ob;
   vector<int> v = {7,8,2,4};
   cout << (ob.longestSubarray(v, 4));
}

Đầu vào 

{7,8,2,4}, 4

Đầu ra 

2