[LeetCode] 122. Best Time to Buy and Sell Stock II - Java

Best Time to Buy and Sell Stock II - LeetCode

 

문제

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 

Constraints:

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

 

가격 배열 prices가 주어지며 여기서 prices[i]는 i일에 주어진 주식의 가격이다.

매일 주식을 구매 또는 판매할 수 있지만, 주식은 최대 1주만 보유할 수 있고, 구매한 당일에도 바로 판매할 수 있다.

얻을 수 있는 최대 profit을 반환하는 문제이다.

 

---

 

내 풀이

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;

        for(int i=1; i<prices.length; i++){
            if(prices[i] > prices[i-1]){
                profit += prices[i] - prices[i-1];
            }
        }

        return profit;
    }
}

121번 Best Time to Buy and Sell Stock 을 푼 뒤여서 그런지 빠르게 풀 수 있었다.

주식을 살 때 그 가격을 이익에서 차감하는 것이 아니기 때문에,

바로 이전의 가격과 비교해서 주식 가격이 내렸다면 바로 판매한다고 가정하고 차익을 이익에 더해주는 형태로 풀이했다.

 

 

• 시간복잡도 : O(n)
• 공간복잡도 : O(1)

 

최적의 코드로 잘 풀이한 것 같다.