資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告