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