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