Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

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

Khái niệm

Cho một mảng số nguyên, nhiệm vụ là xác định hiệu tuyệt đối lớn nhất giữa phần tử nhỏ hơn gần nhất bên trái và bên phải của mỗi phần tử trong mảng. Nếu không có phần tử nhỏ hơn bên trái hoặc bên phải của bất kỳ phần tử nào, ta coi giá trị nhỏ hơn là 0. Ví dụ, với phần tử ngoài cùng bên trái, phần tử nhỏ hơn bên trái được đặt là 0. Tương tự, với phần tử ngoài cùng bên phải, phần tử nhỏ hơn bên phải được đặt là 0.

Đầu vào

arr[] = {3, 2, 9}

Đầu ra

2

Phần tử nhỏ hơn bên trái LS[] {0, 0, 2}

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

Hiệu lớn nhất của abs(LS[i] - RS[i]) = 2 - 0 = 2

Đầu vào

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

Đầu ra

4

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

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

Hiệu lớn nhất của abs(LS[i] - RS[i]) = 8 - 4 = 4

Phương pháp

Giải pháp đơn giản: tìm phần tử nhỏ hơn gần nhất bên trái và bên phải cho mỗi phần tử, sau đó cập nhật hiệu lớn nhất. Độ phức tạp O(n^2).

Giải pháp hiệu quả O(n): sử dụng stack. Phần thú vị là tính cả phần tử nhỏ hơn bên trái và bên phải bằng cùng một hàm.

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

Tìm tất cả phần tử nhỏ hơn bên trái:

  • Tạo stack S rỗng và mảng LS[]
  • Với mỗi phần tử 'Array[i]' từ 0 đến n-1:
    • Khi S không rỗng và đỉnh S >= 'Array[i]': pop S
    • Nếu S rỗng: 'Array[i]' không có phần tử nhỏ hơn trước đó LS[i] = 0
    • Ngược lại: phần tử nhỏ hơn gần nhất là đỉnh stack LS[i] = S.top()
    • Push 'Array[i]' vào S
  • Tìm tất cả phần tử nhỏ hơn bên phải:
    • Đảo ngược mảng Array[]. Sau khi đảo, phần tử nhỏ hơn bên phải trở thành phần tử nhỏ hơn bên trái.
    • Tạo mảng RRS[] và lặp lại các bước 1-2 để điền RRS (thay vì LS).
    • Khởi tạo result = -1. Với mỗi phần tử Array[i], phần tử nhỏ hơn bên phải của mảng đảo được lưu tại RRS[n-i-1]. Cập nhật result = max(result, abs(LS[i] - RRS[n-i-1]))

Ví dụ

// Chương trình C++ tìm hiệu giữa phần tử nhỏ hơn trái và phải
#include<bits/stdc++.h>
using namespace std;

// Hàm điền phần tử nhỏ hơn bên trái cho mỗi phần tử Array[0..n1-1]
void leftSmaller(int Array[], int n1, int SE1[]){
    // Tạo stack rỗng
    stack<int> S1;
    // Duyệt tất cả phần tử mảng
    for (int i=0; i<n1; i++){
        // Loại bỏ đỉnh stack khi đỉnh >= Array[i]
        while (!S1.empty() && S1.top() >= Array[i])
            S1.pop();
        // Lưu phần tử nhỏ hơn của phần tử hiện tại
        if (!S1.empty())
            SE1[i] = S1.top();
        // Nếu tất cả phần tử trong S đều > Array[i]
        else
            SE1[i] = 0;
        // Push phần tử này
        S1.push(Array[i]);
    }
}

// Hàm trả về hiệu lớn nhất giữa phần tử nhỏ hơn trái và phải
int findMaxDiff(int Array[], int n1){
    int LS1[n1]; // Lưu phần tử nhỏ hơn bên trái
    // Tìm phần tử nhỏ hơn bên trái
    leftSmaller(Array, n1, LS1);
    // Tìm phần tử nhỏ hơn bên phải: đảo mảng và làm tương tự
    int RRS1[n1]; // Lưu phần tử nhỏ hơn bên phải trong mảng đảo
    reverse(Array, Array + n1);
    leftSmaller(Array, n1, RRS1);
    // Tìm hiệu tuyệt đối lớn nhất giữa LS1 và RRS1
    // Trong mảng đảo, phần tử nhỏ hơn bên phải của Array[i] lưu tại 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 result1;
}

// Chương trình chính
int main(){
    int Array[] = {3, 5, 9, 8, 8, 10, 4};
    int n = sizeof(Array)/sizeof(Array[0]);
    cout << "Hiệu lớn nhất : " << findMaxDiff(Array, n) << endl;
    return 0;
}

Đầu ra

Hiệu lớn nhất : 4