221117 :: [leetcode] Best Time to Buy and Sell Stock, Number of Zero-Filled Subarrays, Daily Temperatures

Best Time to Buy and Sell Stock

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

 

Constraints:

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

 

시간에 따른 주식 가격 변화를 배열로 받고 최대 이익을 반환하는 문제

 

Solution 1 (시간 초과):

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let maxNum = 0;
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            if (maxNum < prices[j] - prices[i]) {
                maxNum = prices[j] - prices[i];
            }
        }
    }
    return maxNum;
};

• 이중 for문으로 prices 배열 순회

 

Solution 2:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let i = 0;
    let j = 1;
    let maxNum = 0;

    while (j < prices.length) {
        if (prices[i] < prices[j]) {
            let profit = prices[j] - prices[i];
            maxNum = Math.max(maxNum, profit);
        } else {
            i = j;
        }
        j++;
    }
    return maxNum;
};

 

Number of Zero-Filled Subarrays

Given an integer array nums, return the number of subarrays filled with 0.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
Explanation: 
There are 4 occurrences of [0] as a subarray.
There are 2 occurrences of [0,0] as a subarray.
There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.

Example 2:

Input: nums = [0,0,0,2,0,0]
Output: 9
Explanation:
There are 5 occurrences of [0] as a subarray.
There are 3 occurrences of [0,0] as a subarray.
There is 1 occurrence of [0,0,0] as a subarray.
There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.

Example 3:

Input: nums = [2,10,2019]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.

 

0으로 이루어진 하위 배열의 수 반환

=> nums = [1,3,0,0,2,0,0,4]인 경우 [0, 0]이 2개, [0]이 4개이므로 6을 반환한다

 

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var zeroFilledSubarray = function (nums) {
    let curCount = 0;
    let totalCount = 0;
    for (const num of nums) {
        if (num == 0) {
            curCount++;
            totalCount += curCount;
        } else {
            curCount = 0;
        }
    }
    return totalCount;
};

 

Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

 

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

 

Constraints:

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

 

더 따뜻해지려면 기다려야 하는 일수 반환

내일이 더 따뜻하면 1 반환 모레가 더 따뜻하면 2 반환

 

Solution 1 (시간 초과):

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    let result = new Array(temperatures.length).fill(0);
    for (let i = 0; i < temperatures.length; i++) {
        let j = i;
        while (temperatures[j] <= temperatures[i]) {
            result[i]++;
            j++;
            if (j == temperatures.length) result[i] = 0;
        }
    }
    return result;
};

 

Solution 2:

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    let result = new Array(temperatures.length).fill(0);
    const stack = [];

    for (let i = 0; i < temperatures.length; i++) {
        if (i == 0) stack.push([temperatures[i], i]);
        else {
            while (stack.length && stack.at(-1)[0] < temperatures[i]) {
                const prev = stack.pop()[1];
                result[prev] = i - prev;
            }
            stack.push([temperatures[i], i]);
        }
    }
    return result;
};

• stack 사용