C++での分割リスト

numsという整数のリストがあるとすると、左側のすべての数値が厳密に少なくなるように、リストを2つのサブリスト（空ではない）に分割できるかどうかを確認する必要があります。右側のすべての数字よりも。

したがって、入力が[6,4,3,8,10]の場合、left=[6,4,3]およびright=[8,10]

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

• n：=numsのサイズ

• サイズnの配列の権利を定義する

• サイズnの左側の配列を定義します

• left [0]：=nums [0]

• 右の最後の要素：=numsの最後の要素

• 初期化i：=1の場合、i

  • left [i]：=left[i-1]とnums[i]

    の最大値

• 初期化i：=n-2の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • right [i]：=right [i+1]とnums[i]

    の最小値

• 初期化i：=0の場合、i

  • left [i]

    • trueを返す

• falseを返す

理解を深めるために、次の実装を見てみましょう-

例

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

出力

1