在C ++中找到最接近的左侧和右侧较小元素之间的最大差异

概念

对于给定的整数数组，我们的任务是确定数组中每个元素的最左和最右的较小元素之间的最大绝对差。应该注意的是，如果在任何元素的右侧或左侧没有较小的元素，则我们接受零作为较小的元素。在此，例如，对于最左边的元素，将左侧最接近的较小元素设置为0。以同样的方式，对于最右边的元素，将右侧的较小元素设置为0。

输入项

arr[] = {3, 2, 9}

输出结果

左较小的LS [] {0，0，2}

右移较小的RS [] {2，0，0}

Abs的最大差异（LS [i]-RS [i]）= 2-0 = 2

输入项

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

输出结果

左较小的LS [] = {0，3，5，5，5，8，8，3}

右边较小的RS [] = {0，4，8，4，4，4，0}

Abs的最大差异（LS [i]-RS [i]）= 8-4 = 4

方法

我们应用一个简单的解决方案，其中我们的任务是为每个元素找到最接近的左侧和右侧较小元素，然后更新左侧和右侧较小元素之间的最大差异，这将耗费O（n ^ 2）的时间。

同样，我们实现了一个耗费O(n)时间的有效解决方案。在这里，我们实现了一个堆栈。在这里，有趣的部分是我们使用相同的函数计算左变小和右变小。

假设输入数组为“ Array []”，数组大小为“ n”

确定左侧所有较小的元素

建立一个新的空栈S和一个数组LS []
现在，对于输入Array []中的每个元素'Array [i]'，其中'i'从0到n-1。

而S为非空且S的顶部元素大于或等于'Array [i]'：pop S
如果S为空：'Array [i]'没有前面的较小值LS [i] = 0
否则：最接近'Array [i]'的较小值是堆栈的顶部LS [i] = S.top()
将'Array [i]'推到S上
确定右侧所有较小的元素

首先是反向数组Array []。现在，在反转数组之后，右变小。
建立一个数组RRS []并重复步骤1和2以填充RRS（代替LS）。
我们将结果初始化为-1，然后对每个元素Array [i]执行以下操作。对于反向数组，将Array [i]较小的存储在RRS [ni-1]中，返回结果= max（结果，LS [i] -RRS [ni-1]）

示例

// C++ program to find the difference b/w left and
//数组中每个元素的右较小元素
#include<bits/stdc++.h>
using namespace std;
//显示功能以填充每个左侧的较小元素
//数组[0..n1-1]的元素。这些值被填充
//在SE1 [0..n1-1]
void leftSmaller(int Array[], int n1, int SE1[]){
   //建立一个空栈
   stack<int>S1;
   //访问所有数组元素
   //计算每个元素最近的较小元素
   for (int i=0; i<n1; i++){
      //用来不断从S1移除顶部元素，而顶部
      //元素大于或等于Array [i]
      while (!S1.empty() && S1.top() >= Array[i])
      S1.pop();
      //用于存储当前元素的较小元素
      if (!S1.empty())
         SE1[i] = S1.top();
      //已经看到，如果S中的所有元素都大于Array [i]
      else
         SE1[i] = 0;
         //用于推送此元素
         S1.push(Array[i]);
      }
   }
   //显示函数返回最大差异b / w向左＆amp;
   //右边的较小元素
   int findMaxDiff(int Array[], int n1){
      int LS1[n1]; // To store left smaller elements
      //找到每个元素的左侧较小元素
      leftSmaller(Array, n1, LS1);
      // Determine右边的较小元素 of every element
      //首先反转数组并执行相同的过程
      int RRS1[n1]; // Used to store右边的较小元素s in
      //反向数组
      reverse(Array, Array + n1);
      leftSmaller(Array, n1, RRS1);
      // Determine maximum absolute difference b/w LS1 & RRS1
      //在反向数组中，Array [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 maximum difference between LS1 & RRS1
   return result1;
}
//驱动程序
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;
}

输出结果

Maximum diff : 4

基础教程