C ++中的分割清单

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个称为nums的整数列表，我们必须确定是否可以将该列表划分为两个子列表（非空），以使左侧的每个数字严格小于右侧的每个数字。

因此，如果输入类似于[6,4,3,8,10]，则输出为true，因为left = [6,4,3]和right = [8,10]

为了解决这个问题，我们将遵循以下步骤-

  • n：= nums的大小

  • 定义大小为n的数组权

  • 定义一个大小为n的数组

  • 左[0]：=数字[0]

  • 右边的最后一个元素：=数字的最后一个元素

  • 对于初始化i：= 1，当i <n时，更新（将i增加1），-

    • left [i]：= left [i-1]和nums [i]的最大值

  • 对于初始化i：= n-2，当i> = 0时，更新（将i减1），执行-

    • right [i]：= right [i + 1]和nums [i]的最小值

  • 对于初始化i：= 0，当i <n-1，更新（将i增加1）时，执行-

    • 返回真

    • 如果left [i] <right [i + 1]，则-

  • 返回假

让我们看下面的实现以更好地理解-

示例

#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

以上是 C ++中的分割清单 的全部内容， 来源链接： utcz.com/z/347139.html

回到顶部