C++에서 유효한 부분배열의 수

<시간/>

정수 배열 A가 있다고 가정하고 다음 조건을 충족하는 비어 있지 않은 연속 하위 배열의 수를 찾아야 합니다. 하위 배열의 맨 왼쪽 요소는 하위 배열의 다른 요소보다 크지 않습니다.

따라서 입력이 [1,4,2,5,3]과 같으면 출력은 11이 됩니다. 11개의 유효한 하위 배열이 있으므로 [1],[4],[2],[5 ],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2 ,5,3].

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

ret :=0
n :=숫자 크기
하나의 스택 정의
initialize i :=0의 경우, i <숫자의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
- x :=숫자[i]
- 동안(st가 비어 있지 않고 x 를 수행합니다.
  - st
    에서 요소 삭제
- x를 st에 삽입
- ret :=st + ret의 크기
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int validSubarrays(vector<int>& nums) {
      int ret = 0;
      int n = nums.size();
      stack <int> st;
      for(int i = 0; i < nums.size(); i++){
         int x = nums[i];
         while(!st.empty() && x < st.top()) st.pop();
         st.push(x);
         ret += st.size();
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,4,2,5,3};
   cout << (ob.validSubarrays(v));
}

입력

{1,4,2,5,3}