はじめに

---

与えられた配列を，ある条件を満たすように２分割するインデックス番号を答える問題．

分割する条件は，左側の配列のすべての要素が右側の配列のすべての要素よりも小さい事．

分割できる位置が複数ある場合は，左の配列が一番短いものを求める．

作った解法

---

右端からi番目までの要素の最小値をminis[i]にメモし，それを基に分割できる位置を探す，といった解を作った．

コード全体

---

class Solution {
public:
  int partitionDisjoint(vector<int>& nums) {
    vector<int> minis(nums.size());
    minis.back() = nums.back();
    for (int i=nums.size()-2; i!=-1; --i) {
      minis[i] = min(minis[i+1], nums[i]);
    }
    int maximum = 0;
    for (int i=0; i<nums.size()-1; ++i) {
      if (nums[i] <= minis[i+1] && maximum <= minis[i+1]) return i + 1;
      maximum = max(maximum, nums[i]);
    }
    return nums.size()-1;
  }
};

解説

---

関数

---

class Solution {
public:
  int partitionDisjoint(vector<int>& nums) {

ミニ配列の準備

---

上で概要を記した解法で必要な，「右端からi番目までの最小値」を準備．

    vector<int> minis(nums.size());
    minis.back() = nums.back();
    for (int i=nums.size()-2; i!=-1; --i) {
      minis[i] = min(minis[i+1], nums[i]);
    }

分割位置を探す

---

nums[0]からnums[i]までの最大値maximumを更新し続け，nums[i+1]からnums[nums.length()-1]までの最小値であるminis[i+1]より小さいものが見つかった時に，その位置の一つ右のi+1を返す．

    int maximum = 0;
    for (int i=0; i<nums.size()-1; ++i) {
      if (nums[i] <= minis[i+1] && maximum <= minis[i+1]) return i + 1;
      maximum = max(maximum, nums[i]);
    }

おしまい

---

問題の性質上，上記のループで値を返すのでこのreturnは必要ないが，最後にreturnがないと LeetCode 上でコンパイラに怒られるので，書いた．

    return nums.size()-1;
  }
};

おわりに

---

私の解法よりも，左から準備見ていける解法が，LeetCode の Discuss 上で多数公開されているので，併せてそちらも見てほしい．

参考

---

• https://leetcode.com/problems/partition-array-into-disjoint-intervals