长鑫科技

今天是长鑫科技上市的第一天，作为"航母级"的 IPO 案例，而且又是科技大牛市的明星股。

上市首日就破了诸多记录：

• A 股首只开盘市值破 3 万亿的科技股
• 超越中芯国际，科创板市值榜首；超越工商银行，登顶 A 股市值榜首
• A 股首只单日成交额破千亿的个股，同时换手率超 50%，交投活跃度创 A 股新股首日之最

但这些和咱们普通老百姓关系不大，大伙最关心的还是，中一手能赚多少钱。

之前咱们推算的，中一签也就是几千到几万不等，十几万的事情别想了，十倍股也不太可能。

现在结果公布了，一签赚 2 万，涨幅 470% 。

更离谱的是，收盘后开始有人骂了，说这么好的叙事，才涨这么点。

这么说吧，涨得一点都不少了，市值 3 万亿，所有中签投资者总盈利超过 1500 亿，还想怎么样？

那些收盘后大骂的人，大概率不是纯中签的幸运儿，因为没人会嫌 2 万元的红包太小，破口大骂的，大概率是开盘追高冲进去的赌徒。

对此，你怎么看？作为中签率超高的大肉签，你中了吗（反正我没有），又在涨幅多少的时候出掉的呢，欢迎评论区交流。

...

回归主题，来一道和「腾讯」相关的算法题。

题目描述

平台：LeetCode

题号：739

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。

如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]

输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]

输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]

输出: [1,1,0]

提示：

单调栈

抽象题意为 : 求解给定序列中每个位置（右边）最近一个比其大的位置，可使用「单调栈」来进行求解。

具体的，我们可以从前往后处理所有的 ，使用某类容器装载我们所有的「待更新」的位置（下标），假设当前处理到的是 ：

• 若其比容器内的任意位置（下标）对应温度要低，其必然不能更新任何位置（下标），将其也加入容器尾部（此时我们发现，若有一个新的位置（下标）加入容器，其必然是当前所有待更新位置（下标）中的温度最低的，即容器内的温度单调递减）；

• 若其价格高于容器内的任一位置（下标）对应温度，其能够更新容器位置（下标）的答案，并且由于我们容器满足单调递减特性，我们必然能够从尾部开始取出待更新位置来进行更新答案，直到处理完成或遇到第一个无法更新位置。

由于我们需要往尾部添加和取出元素，因此容器可使用「栈」。

Java 代码：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!d.isEmpty() && temperatures[d.peekLast()] < temperatures[i]) {
                int idx = d.pollLast();
                ans[idx] = i - idx;
            }
            d.addLast(i);
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        deque<int> d;
        for (int i = 0; i < n; i++) {
            while (!d.empty() && temperatures[d.back()] < temperatures[i]) {
                int idx = d.back();
                ans[idx] = i - idx;
                d.pop_back();
            }
            d.push_back(i);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n, he, ta = len(temperatures), 0, 0
        ans, stk = [0] * n, [-1] * n
        for i in range(n):
            while he < ta and temperatures[stk[ta - 1]] < temperatures[i]:
                ta -= 1
                idx = stk[ta]
                ans[idx] = i - idx
            stk[ta] = i
            ta += 1
        return ans

TypeScript 代码：

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length
    const ans = new Array<number>(n).fill(0)
    const stk = new Array<number>(n).fill(-1)
    let he = 0, ta = 0
    for (let i = 0; i < n; i++) {
        while (he < ta && temperatures[stk[ta - 1]] < temperatures[i]) {
            const idx = stk[--ta]
            ans[idx] = i - idx
        }
        stk[ta++] = i
    }
    return ans
};

• 时间复杂度：
• 空间复杂度：

最后

巨划算的 LeetCode 会员优惠通道目前仍可用 ~

使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。

我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。