leetcode901. 股票价格跨度

901. 股票价格跨度[题目链接]

难度中等35收藏分享切换为英文关注反馈

编写一个 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) 小于或等于今天的价格。

提示：

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

 

分析:问题很明确，实现类StockSpanner ，一个初始化方式，一个求值方法，next方法需要借助以前调用next(..)的括号中的参数，所以可以在初始化方法的时候，用一个数组全部存起来，然后写Next方法，返回一个int类型值即可，求得是当前日期之前的最大的连续的小于等于当天的价格的连续日数。

问题分析完毕，那么开始 写代码把:

 

首先暴力法，就是数组存起来，每次都从头遍历一遍，数据规模小的时候，肯定能过，数据量大不一定，因为有可能给的数据就是为了恶心你，让你每次都从当前位置j遍历到0...

先贴暴力代码:

class StockSpanner {
	int[] prices;
	int k;
    public StockSpanner() {
        prices = new int[150005];
        k = 0;
    }
    
    public int next(int price) {
    	prices[k++]=price;
    	int res = 0,now=0;
    	for(int j = k-1 ; j >=0 ; j--){
    		now=0;
    		while(j>=0 && prices[j]<=price){
    			j--;
    			now++;
    		}
    		res=Math.max(res, now);
    		break;
    	}
    	return res;
    }
}

但是没想到,过了

 

但既然暴力能过，就先暴力 拿分把

这里贴一份优化后的代码:

求当前日的最大跨度，其实就是找当前日的前面第一个比他大的日期，然后中间的所有都是符合的。所以维护一个单调递减的栈即可，那么如何保存天数的问题呢，可以用结构体或者再另外维护一个栈来解决，都是可以的。

class StockSpanner {
	Stack<Integer> prices = new Stack<Integer>();
	Stack<Integer> days = new Stack<Integer>();
    public StockSpanner() {
    }
    public int next(int price) {
    	int ans = 1;
    	while(!prices.isEmpty() && prices.peek()<=price){
    		prices.pop();
    		ans+=days.pop();
    	}
    	prices.add(price);
    	days.add(ans);
    	return ans;
    }
}

 

效率还是快了不少的