C++ Non DP solution. Using Heap and Linked-list


  • 1
    R

    Time complexity is O(n+(m-k)log(m)). Space is O(m). m is the number of increasing and decreasing intervals in the array.
    First we need need to build a list contains all the increasing and decreasing intervals in the array.
    For example: for the array: [0,1,3,2,4,2,0,5] ,the list is [3,-1,2,-4,5].
    The heap contains all the elements in the list.

    Apparently the maximum profit is the sum of all increasing intervals if the number of increasing intervals is smaller than or equal to k. Therefore the general ideas is to remove some of the increasing intervals until the number of increasing intervals is equal to k.

    Steps:
    1: Delete the decreasing intervals at the front and back of the list.
    2: Find the minimum interval. That interval can be increasing or decreasing. Intervals are compared based on their absolute values.
    2: If the minimum is an increasing interval. merge it with two decreasing intervals before and after it in the list to form a new decreasing interval. If this interval is the first or last element in list then just delete it.
    If the minimum is a decreasing interval. merge it with two increasing intervals before and after it in the list to form a new increasing interval.

    Repeat these steps until the number of increasing intervals is equal to k.

    struct cmp{
        bool operator()(list<int>::iterator a,list<int>::iterator b)const{
            if(abs(*a)==abs(*b))
                return &*a<&*b;
            return abs(*a)<abs(*b);    
        }
    }comp;
    
    class Solution {
    public:
    
     int maxProfit(int k, vector<int>& prices) {
            if(prices.size()<2 || k<1)
                return 0;
            set<list<int>::iterator,cmp> intervalsSet;
            list <int> intervalsList;
            bool inc=(prices[1]-prices[0])>=0;
            int start=prices[0],transc=0,prev=prices[0],profit=0;
            for(int i=1;i<prices.size();i++){
                if(prices[i]-prev<0 && inc){
                    intervalsList.push_back(prev-start);
                    profit=profit-start+prev;
                    transc++;
                    start=prev;
                    inc=!inc;
                }
                if(prices[i]-prev>=0 && !inc){
                    intervalsList.push_back(prev-start);
                    start=prev;
                    inc=!inc;
                }
                prev=prices[i];
            }
            if(inc){
                transc++;
                profit=profit-start+prev;
                intervalsList.push_back(prev-start);
              }
            for(list<int>::iterator it=intervalsList.begin();it!=intervalsList.end();++it)
                intervalsSet.insert(it);
            while(transc>k){
                if(*intervalsList.begin()<0){
                    intervalsSet.erase(intervalsList.begin());
                    intervalsList.pop_front();
                }
                if(intervalsList.back()<0){
                    list<int>::iterator last=intervalsList.end();
                    last--;
                    intervalsSet.erase(last);
                    intervalsList.pop_back();
                }
                list<int>::iterator curr=*intervalsSet.begin();
                profit=profit-abs(*curr);
                transc--;
                list<int>::iterator next=curr;
                next++;
                if(curr!=intervalsList.begin() && next!=intervalsList.end()){
                    list<int>::iterator before=curr;
                    before--;
                    intervalsSet.erase(before);
                    intervalsSet.erase(next);
                    intervalsSet.erase(curr);
                    *curr=*curr+*before+*next;
                    intervalsList.erase(before);
                    intervalsList.erase(next);
                    intervalsSet.insert(curr);
                }
                else{
                    intervalsSet.erase(curr);
                    intervalsList.erase(curr);
                }
            }
    
            return profit;
        }
    };
    

  • 0
    S

    How can you get this greative idea?
    Zei tm niubi !


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.