3010. 將數組分成最小總代價的子數組 I

思路

根據題意，要找到除了第一個數字之外的最小兩個數字，
除了排序後找之外，遍歷一遍記錄下來會更快。

程式碼

找到最小兩個值

class Solution {
public:
    int minimumCost(vector<int>& nums) {
        int b = INT_MAX, c = INT_MAX;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] < b) {
                c = b;
                b = nums[i];
            }
            else if(nums[i] < c) {
                c = nums[i];
            }
        } 
        return nums[0] + b + c;
    }
};

複雜度分析

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