数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找最近左、右较小元素之间的最大差值
概念
对于给定的整数数组，我们的任务是确定每个元素的最近左、右较小元素之间的最大绝对差值。需要注意的是，如果任何元素的右侧或左侧没有较小元素，则我们取零作为较小元素。例如，对于最左边的元素，左侧最近的较小元素设置为 0。同样，对于最右边的元素，右侧的较小元素设置为 0。
输入
arr[] = {3, 2, 9}输出
2
左侧较小元素 LS[] {0, 0, 2}
右侧较小元素 RS[] {2, 0, 0}
最大差值 |LS[i] - RS[i]| = 2 - 0 = 2
输入
arr[] = {3, 5, 9, 8, 8, 10, 4}输出
4
左侧较小元素 LS[] = {0, 3, 5, 5, 5, 8, 3}
右侧较小元素 RS[] = {0, 4, 8, 4, 4, 4, 0}
最大差值 |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]' 时：弹出 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[n-i-1] 中，返回结果 = max(结果, LS[i]-RRS[n-i-1])
示例
// 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;
}输出
Maximum diff : 4
更新于：2020-7-24
255 次浏览
广告