Phần tử lớn hơn trước đó trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng. Nhiệm vụ của chúng ta là trả về phần tử lớn nhất đứng trước phần tử hiện tại trong mảng, nếu không thì in ra -1.

Hãy lấy một ví dụ để hiểu vấn đề

Input: {6, 2, 7, 1, 5, 3}
Output: -1, 6, -1, 7, 7, 7

Để giải quyết vấn đề này, một giải pháp dễ dàng và rõ ràng sẽ là sử dụng các vòng lặp lồng nhau sẽ kiểm tra phần tử lớn hơn trong phần trước của mảng.

Chương trình cho thấy việc triển khai giải pháp của chúng tôi

Ví dụ

#include <iostream>
using namespace std;
void preceddingGreatestElement(int arr[], int n){
   cout << "-1\t";
   int i, j;
   for (i = 1; i < n; i++) {
      for (j = i-1; j >= 0; j--) {
         if (arr[i]<arr[j]) {
            cout<<arr[j]<< "\t";
            break;
         }
      }
      if (j == -1)
      cout << "-1\t";
   }
}
int main() {
   int arr[] = { 6, 2, 7, 1, 12, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   preceddingGreatestElement(arr, n);
   return 0;
}

Đầu ra

-1   6   -1   7   -1   12

Một giải pháp hiệu quả hơn để giải quyết vấn đề của chúng tôi là sử dụng cấu trúc dữ liệu ngăn xếp. Và duy trì số lớn hơn trước ở đầu ngăn xếp.

Chương trình cho thấy việc thực hiện giải pháp này

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void preceddingGreatestElement(int arr[], int n) {
   stack<int> elements;
   elements.push(arr[0]);
   cout << "-1\t";
   for (int i = 1; i < n; i++) {
      while (elements.empty() == false && elements.top() < arr[i])
      elements.pop();
      if(elements.empty())
         cout<<"-1\t";
      else
         cout<<elements.top()<<"\t";
      elements.push(arr[i]);
   }
}
int main() {
   int arr[] = { 6, 2, 7, 1, 12, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   preceddingGreatestElement(arr, n);
   return 0;
}

Đầu ra

-1   6   -1   7   -1   12