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

Tìm chênh lệch tối đa giữa các phần tử nhỏ hơn bên trái và bên phải gần nhất trong C ++

Khái niệm

Đối với một mảng số nguyên cho trước, nhiệm vụ của chúng ta là xác định độ chênh lệch tuyệt đối lớn nhất giữa phần tử nhỏ hơn bên trái và bên phải gần nhất của mọi phần tử trong mảng. bên của bất kỳ phần tử nào thì chúng tôi chấp nhận số không là phần tử nhỏ hơn. Ở đây, chẳng hạn đối với phần tử ngoài cùng bên trái, phần tử nearestsmaller ở phía bên trái được đặt là 0. Tương tự như vậy, đối với các phần tử ngoài cùng bên phải, phần tử nhỏ hơn ở phía bên phải được đặt là 0.

Đầu vào 

arr[] = {3, 2, 9}

Đầu ra 

2

Trái LS nhỏ hơn [] {0, 0, 2}

RS nhỏ hơn bên phải [] {2, 0, 0}

Chênh lệch tối đa của abs (LS [i] - RS [i]) =2 - 0 =2

Đầu vào 

arr[] = {3, 5, 9, 8, 8, 10, 4}

Đầu ra 

4

LS nhỏ hơn bên trái [] ={0, 3, 5, 5, 5, 8, 3}

RS nhỏ hơn bên phải [] ={0, 4, 8, 4, 4, 4, 0}

Chênh lệch tối đa của abs (LS [i] - RS [i]) =8 - 4 =4

Phương pháp

Chúng tôi áp dụng một giải pháp đơn giản trong đó nhiệm vụ của chúng tôi là tìm phần tử nhỏ hơn bên trái và bên phải gần nhất trước phần tử và sau đó cập nhật sự khác biệt tối đa giữa phần tử nhỏ hơn bên trái và bên phải, điều này tiêu tốn O (n ^ 2) thời gian.

Một lần nữa, chúng tôi thực hiện một giải pháp hiệu quả tiêu tốn O (n) thời gian. Ở đây, chúng tôi triển khai một ngăn xếp. Ở đây, phần thú vị ở đây là chúng tôi tính toán cả bên trái nhỏ hơn và bên phải nhỏ hơn bằng cách sử dụng cùng một hàm.

Giả sử mảng đầu vào là 'Array []' và kích thước của mảng là 'n'

Xác định tất cả phần tử nhỏ hơn ở phía bên trái

  • Xây dựng một ngăn xếp trống mới S và một mảng LS []
  • Bây giờ đối với mọi phần tử 'Array [i]' trong đầu vào Array [], trong đó 'i' đi từ 0 đến n-1.
    • while S không rỗng và phần tử trên cùng của S lớn hơn hoặc bằng 'Array [i]':pop S
    • nếu S trống:'Array [i]' không có giá trị nhỏ hơn nào đứng trướcLS [i] =0
    • else:giá trị nhỏ hơn gần nhất của 'Array [i]' là topof stackLS [i] =S.top ()
    • đẩy 'Array [i]' vào S
    • Xác định tất cả các phần tử nhỏ hơn ở phía bên phải
  • Lúc đầu đảo ngược mảng Array []. Bây giờ sau khi đảo ngược mảng, bên phải nhỏ hơn trở nên nhỏ hơn bên trái.
  • Xây dựng một RRS mảng [] và lặp lại các bước 1 và 2 để lấp đầy RRS (thay thế LS).
  • Chúng tôi khởi tạo kết quả là -1 và thực hiện theo sau cho mọi elementArray [i]. Đối với mảng đảo ngược bên phải nhỏ hơn cho Mảng [i] được lưu trữ ở RRS [n-i-1] return result =max (result, LS [i] -RRS [n-i-1])

Ví dụ 

// C++ program to find the difference b/w left and
// right smaller element of every element in array
#include<bits/stdc++.h>
using namespace std;
// Shows function to fill left smaller element for every
// element of Array[0..n1-1]. These values are filled
// in SE1[0..n1-1]
void leftSmaller(int Array[], int n1, int SE1[]){
   // Build an empty stack
   stack<int>S1;
   // Visit all array elements
   // Calculate nearest smaller elements of every element
   for (int i=0; i<n1; i++){
      // Used to keep removing top element from S1 while the top
      // element is greater than or equal to Array[i]
      while (!S1.empty() && S1.top() >= Array[i])
      S1.pop();
      // Used to store the smaller element of current element
      if (!S1.empty())
         SE1[i] = S1.top();
      // It has been seen that if all elements in S were greater than Array[i]
      else
         SE1[i] = 0;
         // Used to push this element
         S1.push(Array[i]);
      }
   }
   // Shows function returns maximum difference b/w Left &
   // right smaller element
   int findMaxDiff(int Array[], int n1){
      int LS1[n1]; // To store left smaller elements
      // find left smaller element of every element
      leftSmaller(Array, n1, LS1);
      // Determine right smaller element of every element
      // first reverse the array and do the same process
      int RRS1[n1]; // Used to store right smaller elements in
      // reverse array
      reverse(Array, Array + n1);
      leftSmaller(Array, n1, RRS1);
      // Determine maximum absolute difference b/w LS1 & RRS1
      // In the reversed array right smaller for Array[i] is
      // stored at RRS1[n1-i-1]
   int result1 = -1;
   for (int i=0 ; i< n1 ; i++)
   result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i]));
   // return maximum difference between LS1 & RRS1
   return result1;
}
// Driver program
int main(){
   int Array[] = {3, 5, 9, 8, 8, 10, 4};
   int n = sizeof(Array)/sizeof(Array[0]);
   cout << "Maximum diff : "
   << findMaxDiff(Array, n) << endl;
   return 0;
}

Đầu ra 

Maximum diff : 4