C++의 최대 너비 램프

<시간/>

정수 배열 A가 있다고 가정하고 램프는 i

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

배열 v 생성, 주어진 배열의 n :=크기 설정, ret :=0 설정
스택 정의
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]

C++의 최대 너비 램프

예시

입력

출력