O(n) using two stacks.


  • 1
    V

    The idea is to have two stacks. One for holding the buying prices and one for holding the selling prices. One price in the buy queue corresponds to a sell prices in the sell queue of the transaction is complete.

    We have the following cases:

    • If we did not do anything yet (i.e., the buy stack is empty), buy it.
    • If we have no unsold stock. That is, buyQueue.size() == sellQueue.size(), we have the option to regret a low sell if current price is higher than the price we sold the last share.
      • If current price is higher than the price we sold the last share, regret the last sell and sell today.
      • If current price is lower than the price we sold the last share - fee, buy it. Buying a share with price higher than the last sold price - fee is not optimal as we will need a price that is at least greater than the last sold price to make profit for this purchase in the future. If that is the case, why not sell the previous share on that day? Doing that, we save the fee.
    • If we have unsold stock, that is buyQueue.size() > sellQueue.size():
      • If current price is lower than the price we bought for the last share, we regret that purchase and instead buy today.
      • If selling the unsold share at current price have profit, sell it.

    Finally, we will end up either each buy has a corresponding sell OR we have an unsold share, which should simply be discarded. Then the profit is the difference - fee for each transaction.

    public int maxProfit(int[] prices, int fee) {
            Stack<Integer> buy = new Stack<>();
            Stack<Integer> sell = new Stack<>();
            for (int p : prices) {
                if (buy.isEmpty()) {  //have nothing, buy it
                    buy.push(p);
                } else if (buy.size() == sell.size()) {  //no unsold stock
                    if (p < sell.peek() - fee) {  //current price needs a price lower than the previous sold price to sell in the future, buy it.
                        buy.push(p);
                    } else if (p > sell.peek()) {  //selling at current price for the last transaction can have higher profit, regret the last sell.
                        sell.pop();
                        sell.push(p);
                    }
                } else {  // have an unsold share
                    if (p > buy.peek() + fee) {  //if selling at current price have profit, do it.
                        sell.push(p);
                    } else if (p < buy.peek()) {  //if current price is lower than the most recent purchase, regret it and buy today.
                        buy.pop();
                        buy.push(p);
                    }
                }
            }
            if (buy.size() > sell.size()) {  //discard the unsold buy attempt
                buy.pop();
            }
            int amount = 0;
            while (!buy.isEmpty()) {
                amount += sell.pop() - buy.pop() - fee;
            }
            return amount;
        }
    
    

Log in to reply
 

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