Leetcode-915 Partition Array into Disjoint Intervals(分割数组)

时间:2021-09-02 23:17:26
 1 class Solution
 2 {
 3     public:
 4         int partitionDisjoint(vector<int>& A)
 5         {
 6             if(A.size()==2&&A[0]<=A[1])
 7                 return 1;
 8             vector<int> B(A.size(),0);
 9             
10             int Min = 10000000;
11             for(int i = A.size()-1;i >= 0;i --)
12             {
13                 if(A[i]<Min)
14                 {
15                     B[i] = A[i];
16                     Min = A[i];
17                 }
18                 else
19                     B[i] = Min;
20             }
21             
22         //    for(auto d:B)
23         //        cout << d << " ";
24         //        cout << endl;
25             int result = 0;
26             int Max = A[0];
27             for(int i = 0;i < A.size();i ++)
28             {
29                 if(Max <= B[i])
30                 {
31                     result = i;
32                     break;
33                 }
34                 if(A[i]>Max)
35                 {
36                     Max = A[i];
37                 }
38             }
39             if(result==0)
40                 result = 1;
41             return result;
42         }
43 };