関小君刷题记

题目大意：

股票价格跨度

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

提示：

• 调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
• 每个测试用例最多可以调用  10000 次 StockSpanner.next。
• 在所有测试用例中，最多调用 150000 次 StockSpanner.next。
• 此问题的总时间限制减少了 50%。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=901

解题思路分析：

这道题我们需要利用到2个数组，一个记录所有数字nums[]，另一个用来记录每个数字前面连续小于等于自身数字的个数preSmallCount[]。next方法中，我们比较当前数字与前一数字的大小，如果当前数字小于前一个数字，说明除了当前数字之外没有连续小于自身的数字，此时返回1，并且preSmallCount[index]设置为1。反之，如果当前数字大于等于前一个数字，那么当前数字也必定大于等于preSmallCount[index-1]（连续小于等于前一个数字的个数）这些数字。接下来我们再将index向前移动preSmallCount[index-1]位，再用新的index与当前数字比较，重复上述过程，直到index小于0或者当前数字小于index所指向的数字为止。我们将得到的长度length存入当前preSmallCount[index]中，并返回该length。

实现代码：

// 记录所有数字
int[] nums = new int[10000]; 
// 记录每一个数字前面连续小于等于自身的数量
int[] preSmallCount = new int[10000];
int index=0; // 当前下标
public StockSpanner() {

}

public int next(int price) {
    nums[index]=price; // 将price插入当前下标
    if(index==0){ // 如果当前是首位
        // 当前数字前面连续小于等于自身的长度为1。当前数字自身
        preSmallCount[index]=1;
        index++; // 下标加一
        return 1; // 返回1
    }
    int preIndex=index-1; // 前一个数字的下标
    int length=1; // 连续长度
    // 找到连续小于等于自身的长度
    while(preIndex>=0&&price>=nums[preIndex]){
        length+=preSmallCount[preIndex];
        preIndex-=preSmallCount[preIndex];
    }
    if(price>=nums[index-1]){
        preSmallCount[index]=length;
    }else{
        preSmallCount[index]=1;
    }
    index++;
    return length;
}

本题解法执行时间为33ms。

Runtime: 33 ms, faster than 15.98% of Java online submissions for Online Stock Span.

Memory Usage: 93.3 MB, less than 10.00% of Java online submissions for Online Stock Span.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-901-online-stock-span-解题思路分析/