C++での最大幅ランプ

整数の配列Aがあるとすると、ランプはi

これを解決するには、次の手順に従います-

• 配列vを作成し、n：=指定された配列のサイズを設定し、ret：=0

  を設定します。

• スタックstを定義する

• 0からn–1の範囲のiの場合

  • stが空の場合、またはスタックトップ要素> A [i]の場合は、iをst

    に挿入します。

• for i：=n –1からret+ 1

  • stが空ではなく、stの先頭<=A [i]

    • ret：=retの最大値と（i – stの上部）

    • stから削除

• 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