C ++中的最大宽度斜坡
假设我们有一个整数数组A，斜波是一个元组(i,j)，其中i<j并且A[i]<=A[j]。这样的斜坡的宽度是j-i。我们必须找到A中斜坡的最大宽度。如果不存在，则返回0。因此，如果输入为[6,0,8,2,1,5]，则输出为4。在(i,j)=(1,5)且A[1]=0且A[5]=5时达到最大宽度斜坡
为了解决这个问题，我们将遵循以下步骤-
创建一个数组v，设置n：=给定数组的大小，设置ret：=0
定义一个堆栈st
对于i，范围为0至n–1
如果st为空或堆栈顶部元素>A[i]，则将i插入st
对于i：=n–1向下恢复+1
ret：=ret的最大值和（i–st的顶部）
从st删除
当st不为空且st的顶部<=A[i]
从st删除
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxWidthRamp(vector<int>& A) {
vector < pair <int, int> > v;
int n = A.size();
int ret = 0;
stack <int> st;
for(int i = 0; i < n; i++){
if(st.empty() || A[st.top()] > A[i]){
st.push(i);
}
}
for(int i = n - 1; i > ret; i--){
while(!st.empty() && A[st.top()] <= A[i]){
ret = max(ret, i - st.top());
st.pop();
}
}
return ret;
}
};
main(){
vector<int> v1 = {6,0,8,2,1,5};
Solution ob;
cout << (ob.maxWidthRamp(v1));
}输入值
[6,0,8,2,1,5]
输出结果
4