3698. 分割數組得到的最小絕對差

思路

根據題目要求，要將子數組切分成兩個子數組，left嚴格遞增，right另一個嚴格遞減。
根據題目提供的範例測資，先遞減再遞增的數組不能切分，也就是left數組就得在左邊，right數組就得在右邊。

right數組從左邊到右邊看是遞減，反過來看則是遞增，跟left數組正著看是一樣的。

如果一個數組能被拆成left跟right，那麼整個數組畫在一個二維平面上，
橫軸是座標，縱軸是數值，會變成一個「山形」的圖案，最大的數值在山峰。
因為需要滿足嚴格遞增與遞減，left跟right都不會有重複出現的元素，因此山峰的數值，最多只能重複兩次，

歸納出了上面的想法，我們能用雙指針去找到

• 自左往右遞增後，結尾的位置i，0 ~ i - 1是left。
• 自右往左遞增後，結尾的位置j，j + 1 ~ n - 1 是 right。

最後，根據雙指針最後的位置判斷是否能正常切開。

1. 一般山形，中間的數值能分配到left，亦能分配給right。
2. 山峰數值重複一次，left跟right都分到相同的山峰數值，兩者相減的數值不會變化。
3. 山峰數值重複多次，無法正確切開。

程式碼

class Solution {
public:
    long long splitArray(vector<int>& nums) {
        int n = nums.size();
        long long left = nums[0], right = nums.back();
        int i = 1, j = n - 2;
        while(i < n && nums[i - 1] < nums[i]) {
            left += nums[i];
            ++i;
        }
        while(j >= 0 && nums[j] > nums[j + 1])  {
            right += nums[j];
            --j;
        }
        long long diff = left - right;
        if(i - 1 < j) return -1; // 狀況三
        if(i - 1 == j) return abs(diff); // 狀況二
        return min(abs(diff + nums[i - 1]), abs(diff - nums[i - 1])); // 狀況一
    }
};

判斷複雜度

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$