Approach

# 模擬，每次掃描陣列找最小值相加，將陣列變成非嚴格遞增陣列

Time Complexity

O(n * n)

Space Complexity

O(1)

Code

class Solution {
public:
    bool isSorted(const vector<int> nums) {
        for (int i = 0 ;  i < nums.size() - 1 ; i++) {
            if (nums[i] > nums[i + 1]) {
                return false;
            }
        }

        return true;
    }

    int minimumPairRemoval(vector<int>& nums) {
        int sum = 0;

        while (!isSorted(nums) && nums.size() > 1) {
            int mini = 2147483647, where = -1;

            for (int i = 0 ; i < nums.size() - 1 ; i++) {
                int currentSum = nums[i] + nums[i + 1];

                if (currentSum < mini) {
                    mini = currentSum;
                    where = i;
                }
            }

           if (where != -1) {
                nums[where] = mini;
                nums.erase(nums.begin() + where + 1);
                sum++;
            }
        }

        return sum;
    }
};