알고리즘/leetcode
Partition Array into Disjoint Intervals
유이얼
2021. 7. 22. 23:00
class Solution {
public:
int partitionDisjoint(vector<int>& nums) {
int size = nums.size();
vector<int> forward(size);
vector<int> backward(size);
backward[size - 1] = nums[size - 1];
for (int i = size - 2; i >= 0; --i)
backward[i] = min(backward[i + 1], nums[i]);
forward[0] = nums[0];
for (int i = 0; i < size - 1; ++i) {
if (i > 0)
forward[i] = max(forward[i - 1], nums[i]);
if (forward[i] <= backward[i + 1])
return i + 1;
}
return 0;
}
};
class Solution {
public:
int partitionDisjoint(vector<int>& nums) {
int size = nums.size();
int max_ = nums[0];
int cur_ = nums[0];
int ans = 1;
for (int i = 1; i < size; ++i) {
if (cur_ > nums[i]) {
ans = i + 1;
cur_ = max_;
}
max_ = max(max_, nums[i]);
}
return ans;
}
};