資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式中左側和右側下一個較大數的索引最大乘積
在這個問題中，我們給定一個數組arr[]。我們的任務是建立一個程式來計算左側和右側下一個較大數的索引的最大乘積。
問題描述 −
對於給定的陣列，我們需要找到left[i]*right[i] 的最大值乘積。這兩個陣列定義如下：
left[i] = j, such that arr[i] <’. ‘ arr[j] and i > j. right[i] = j, such that arr[i] < arr[j] and i < j. *The array is 1 indexed.
讓我們來看一個例子來理解這個問題，
輸入
arr[6] = {5, 2, 3, 1, 8, 6}輸出
15
解釋
Creating left array,
left[] = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}
Index products :
1 −> 0*5 = 0
2 −> 1*3 = 3
3 −> 1*5 = 5
4 −> 3*5 = 15
5 −> 0*0 = 0
6 −> 0*5 = 0最大乘積
15
解決方案 −
為了找到左側和右側較大元素索引的最大乘積，我們將首先找到左側和右側較大元素的索引，並將它們的乘積儲存起來以進行比較。
現在，為了找到左側和右側最大的元素，我們將逐一檢查左側和右側索引中大於給定元素的元素。為了查詢，我們將使用棧，並執行以下操作：
If stack is empty −> push current index, tos = 1. Tos is top of the stack Else if arr[i] > arr[tos] −> tos = 1.
使用此方法，我們可以找到陣列左側和右側所有大於給定元素的元素的索引值。
示例
程式說明了解決方案的工作原理：
#include <bits/stdc++.h>
using namespace std;
int* findNextGreaterIndex(int a[], int n, char ch ) {
int* greaterIndex = new int [n];
stack<int> index;
if(ch == 'R'){
for (int i = 0; i < n; ++i) {
while (!index.empty() && a[i] > a[index.top() − 1]) {
int indexVal = index.top();
index.pop();
greaterIndex[indexVal − 1] = i + 1;
}
index.push(i + 1);
}
}
else if(ch == 'L'){
for (int i = n − 1; i >= 0; i−−) {
while (!index.empty() && a[i] > a[index.top() − 1]) {
int indexVal = index.top();
index.pop();
greaterIndex[indexVal − 1] = i + 1;
}
index.push(i + 1);
}
}
return greaterIndex;
}
int calcMaxGreaterIndedxProd(int arr[], int n) {
int* left = findNextGreaterIndex(arr, n, 'L');
int* right = findNextGreaterIndex(arr, n, 'R');
int maxProd = −1000;
int prod;
for (int i = 1; i < n; i++) {
prod = left[i]*right[i];
if(prod > maxProd)
maxProd = prod;
}
return maxProd;
}
int main() {
int arr[] = { 5, 2, 3, 1, 8, 6};
int n = sizeof(arr) / sizeof(arr[1]);
cout<<"The maximum product of indexes of next greater on left and
right is "<<calcMaxGreaterIndedxProd(arr, n);
return 0;
}輸出
The maximum product of indexes of next greater on left and right is 15
更新於：2020年12月9日
293 次瀏覽
廣告