C++의 분할 목록

nums라는 정수 목록이 있다고 가정하면 목록을 두 개의 하위 목록(비어 있지 않음)으로 분할하여 왼쪽 부분의 모든 숫자가 완전히 더 작아지도록 할 수 있는지 여부를 찾아야 합니다. 오른쪽 부분의 모든 숫자보다.

따라서 입력이 [6,4,3,8,10]과 같으면 왼쪽 =[6,4,3] 및 오른쪽 =[8,10]

과 같이 출력이 true가 됩니다.

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

n :=숫자 크기
n
크기의 오른쪽 배열 정의
크기가 n
인 배열을 정의합니다.
왼쪽[0] :=숫자[0]
오른쪽의 마지막 요소 :=숫자의 마지막 요소
initialize i :=1의 경우, i
- left[i] :=left[i - 1] 및 nums[i]
  의 최대값
초기화 i :=n - 2의 경우 i>=0일 때 업데이트(i 1만큼 감소), −
- right[i] :=right[i + 1] 및 nums[i]
  의 최소값
initialize i :=0의 경우, i
- 왼쪽[i] <오른쪽[i + 1]이면 -
  - true를 반환
거짓 반환

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(vector<int> &nums) {
      int n = nums.size();
      vector<int> right(n);
      vector<int> left(n);
      left[0] = nums[0];
      right.back() = nums.back();
      for (int i = 1; i < n; i++) {
         left[i] = max(left[i - 1], nums[i]);
      }
      for (int i = n - 2; i >= 0; i--) {
         right[i] = min(right[i + 1], nums[i]);
      }
      for (int i = 0; i < n - 1; i++) {
         if (left[i] < right[i + 1])
         return true;
      }
      return false;
   }
};
main() {
   Solution ob;
   vector<int> v = {6,4,3,8,10};
   cout << (ob.solve(v));
}

입력

{6,4,3,8,10}