day14：121. 买卖股票的最佳时机、56. 合并区间、135. 分发糖果

day14题目：121. 买卖股票的最佳时机、56. 合并区间、135. 分发糖果

学习计划链接：冲刺春招-精选笔面试 66 题大通关

今日知识点：数组、动态规划、排序等，难度为简单、中等、困难

昨日题目链接：冲刺春招-精选笔面试 66 题大通关 day13

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入： [7,1,5,3,6,4]
输出： 5
解释： 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入： prices = [7,6,4,3,1]
输出： 0
解释： 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 10^5

• 0 <= prices[i] <= 10^4

思路

思路非常非常之清晰啊，因为本质上就是最小值与最大值的一个差让其最大化，且最大值必须在最小值之后出现，所以我们

• 用 minp 记录当前最小值，ans 记录最大利润

  • 若当前 price[i] <= minp，则更新 minp

  • 否则，记录最大利润，ans = max(ans, prices[i]-minp)

代码

/**
 * @param {number[]} prices
 * @return {number}
 */
 var maxProfit = function(prices) {
    let len = prices.length;
    let ans = 0;
    let minp = Number.MAX_VALUE;
    for(let i = 0; i < len; ++i) {
        if(prices[i] <= minp) minp = prices[i];
        else ans = Math.max(ans, prices[i]-minp);
    }
    return ans;
};

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入： intervals = [[1,3],[2,6],[8,10],[15,18]]
输出： [[1,6],[8,10],[15,18]]
解释： 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入： intervals = [[1,4],[4,5]]
输出： [[1,5]]
解释： 区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= starti <= endi <= 10^4

思路

思路非常的清晰啊，因为要合并区间，所以需要先按照每个区间左端点大小升序排列（这样就可以每次与左边的合并即可）

• 排序 intervals.sort((a, b) => { return a[0] - b[0]; });

• 用 ans 存结果区间数组，以 k 记录 ans 当前下标

• 每次设 [prel, prer] = ans[k]、[l, r] = intervals[i];

• 因为排过序了，所以 prel <= l 是必然成立的

  • 只需要判断当前区间左端点 l 与上一个区间右端点 prer 之间关系

  • 若 l > prer则 无需合并，push 之后 ++k，否则进行一个合并，更改区间右端点。

代码

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals.sort((a, b) => { return a[0] - b[0]; });
    let ans = [intervals[0]];
    let k = 0;
    let len = intervals.length;
    for(let i = 1; i < len; ++i) {
        let [prel, prer] = ans[k];
        let [l, r] = intervals[i];
        if(l > prer) {
            ans.push(intervals[i]);
            ++k;
        } else ans[k][1] = Math.max(prer, r);
    }
    return ans;
};

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。

• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入： ratings = [1,0,2]
输出： 5
解释： 你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入： ratings = [1,2,2]
输出： 4
解释： 你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length

• 1 <= n <= 2 * 10^4

• 0 <= ratings[i] <= 2 * 10^4

思路

由题意易知 每个孩子要跟左右两边个比较一次，那么我们从左往右扫一遍，然后再从右往左扫一遍取最大即可

• 从左往右，l[i] 存储 i 孩子与左边的比较后所需最少糖果数，若 ratings[i] > ratings[i-1] 则 l[i] = l[i-1]+1 ，这里需要用数组暂存是因为接下来要跟右边比较

• 从右往左，r 记录 i 孩子与右边比较后所需最少糖果数，若 ratings[i] > ratings[i+1] 则 ++r，否则 r = 1，之后与 l[i] 比较二者取较大的一个数作为该孩子所需最少糖果数

代码

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let len = ratings.length;
    let l = new Array(len).fill(1);
    for(let i = 0; i < len; ++i) 
        if(i-1 >= 0 && ratings[i] > ratings[i-1]) 
            l[i] = l[i-1]+1;
    let [ans, r] = [0, 1];
    for(let i = len-1; i >= 0; --i) {
        if(i < len-1 && ratings[i] > ratings[i+1])
            ++r;
        else r = 1;
        ans += Math.max(l[i], r);
    }
    return ans;
};