Description

Submission

class Solution {
    struct SegTreeNode {
        pair<int, int> info; // min_value, index
        SegTreeNode* left;
        SegTreeNode* right;
        int beg;
        int end;
        SegTreeNode(pair<int,int> info, SegTreeNode* left, SegTreeNode* right, int beg, int end)
            :
            info(info), left(left), right(right), beg(beg), end(end)
            {}
    };

    SegTreeNode* Init(int a, int b) {
        if(a == b) {
            return new SegTreeNode({nums[a], a}, nullptr, nullptr, a, b);
        } 
        int mid = (a + b) / 2;
        SegTreeNode* left = Init(a, mid);
        SegTreeNode* right = Init(mid + 1, b);
        return new SegTreeNode(min(left->info, right->info), left, right, a, b);
    }

    // get the index with the minimum value in range
    pair<int, int> QueryRange(SegTreeNode* node, int a, int b) {
        if(a > node->end || b < node->beg) return {INT_MAX, -1};
        if(a <= node->beg && b >= node->end) return node->info;
        return min(QueryRange(node->left, a, b), QueryRange(node->right, a, b));
    }

    
    int util(int base, int a, int b) {
        if(a > b) return 0;
        auto [minVal, index] = QueryRange(root, a, b);
        if(minVal == INT_MAX) return 0;
        return (minVal - base) + util(minVal, a, index-1) + util(minVal, index + 1, b);
    }
    SegTreeNode *root;
    vector<int> nums;
    int n;
public:
    int minNumberOperations(vector<int>& target) {
        nums = target;
        n = nums.size();
        root = Init(0, n - 1);
        return util(0, 0, n - 1);
    }   
};

class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        int prev = 0, ret = 0;
        for(auto x: target) {
           if(x > prev) ret += x - prev;
           prev = x;
        }
        return ret;
    }
};

Submission

class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        int ret = 0;
        target.insert(target.begin(), 0);
        for(int i = 1; i < target.size(); ++i) {
           ret += max(target[i] - target[i-1], 0);
        }
        return ret;
    }
};