Chiều rộng tối đa trong C ++

Giả sử chúng ta có một mảng A gồm các số nguyên, một đoạn đường nối là một bộ (i, j) mà i

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một mảng v, đặt n:=kích thước của mảng đã cho, đặt ret:=0

• xác định một ngăn xếp

• cho tôi trong phạm vi từ 0 đến n - 1

  • nếu st trống hoặc phần tử trên cùng của ngăn xếp> A [i], thì hãy chèn i vào st

• for i:=n - 1 xuống ret + 1

  • trong khi st không trống và đầu st <=A [i]

    • ret:=max of ret và (i - top of st)

    • xóa khỏi st

• xóa khỏi st

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[6,0,8,2,1,5]

Đầu ra

4