编写一个 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%。
\n
👍 127👎 0
题解
看题目。好像很简单。一直往前叠加计数么。
import java.util.ArrayList;
import java.util.LinkedList;
//leetcode submit region begin(Prohibit modification and deletion)
class StockSpanner {
private ArrayList<Integer> list;
public StockSpanner() {
list = new ArrayList<>();
}
public int next(int price) {
int count = 1;
for (int i = list.size()-1; i >=0 ; i--) {
if (list.get(i)>price){
break;
}
count++;
}
list.add(price);
return count;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner obj = new StockSpanner();
* int param_1 = obj.next(price);
*/
//leetcode submit region end(Prohibit modification and deletion)
提交，看结果。
解答成功:
执行耗时:572 ms,击败了12.05% 的Java用户
内存消耗:47.6 MB,击败了9.54% 的Java用户
emmmmmmmmm，恶魔妈妈木木木木木木木。。。。。应该离超时不远了。
但是其实想一想，回过头来看下代码。每次next的时候，其实是执行的操作是，往结尾插入一个新数据，并往前找到第一个比自己大的值，结果已经很明显了， 另外再维护一份单调性递减的栈数据，十分清晰的空间换时间。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
//leetcode submit region begin(Prohibit modification and deletion)
class StockSpanner {
private ArrayList<Integer> list;
private Stack<Integer> stack;
public StockSpanner() {
list = new ArrayList<>();
stack = new Stack<>();
}
public int next(int price) {
int count = 1;
list.add(price);
int index = list.size()-1;
if (stack.isEmpty()){
stack.push(index);
}else{
//等值的时候的情况也要考虑
while (!stack.isEmpty() && price >= list.get(stack.peek())){
stack.pop();
if (stack.isEmpty()){
count = index + 1;
}else{
count = index - stack.peek();
}
}
stack.push(index);
}
return count;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner obj = new StockSpanner();
* int param_1 = obj.next(price);
*/
//leetcode submit region end(Prohibit modification and deletion)
结果
解答成功:
执行耗时:29 ms,击败了89.06% 的Java用户
内存消耗:45.9 MB,击败了99.10% 的Java用户
2022年10月21日更新下
这么来说
[100, 80, 60, 70, 60, 75, 85]
面对这样的数据的时候
- 拿到了一个100，往前看没有数据，此时应当返回1
- 第二次拿到了80，往前看只能看到一个数字100，比80大，此时应当返回1
- 第三次，拿到了数字60，继续往前看，直接就遇到了80，还是返回1
- 第四次，拿到了数字70，往前可以看到一个数字60，此时结果值应当加1，再往前，遇到了数字80了，比70大，返回结果2
- 再次遇到60，结果依旧返回1
- 遇到75，往前看到60，结果次数加1，再往前看到70，依旧比75小，但是之前我们知道之前遇到数字70的时候得到过结果2，那么就表示在数字70之前，有比70小的数字，和这个70组成连续区间的长度为2，那么结果再加上2。之后再继续往前找，直到找到比数字75大的数字，那么最终结果返回4
- 最后拿到数字85，往前找到了前一个数字75，根据上一步的结果，我们知道了75之前有一段长度为4的连续区间是小于等于75的，那么也必然是小于85的，那么给结果直接加4，并可以跳过这个数字4对应的从60开始到75的这段区间。再继续往前，遇到了80，比85小，依旧可以继续加1，直到遇到了， 数字100之后结束，返回结果6
完成分析之后
第一个问题，在经过了上面的分析过程之后，我们可以很清除的明白了这里的运算逻辑，而单调栈的特性非常完美的契合了这个场景。以最快的速度，找到当前数字之前比这个数字大的数字。
第二个问题，在上面的计算过程中，我们需要记得之前的数字对应的他前面的单调递增区间的长度，又因为每天的价格是可以重复的，那么此时就不然选择Map结构来记录某天价格和区间长度的对应的值
此时有两个选择：
- 我们在解决第一个问题时候用到的单调栈的存储结构中，同时记录他的跨度值，即对应长度
- 另外用一个能跟单调栈同步弹出/压入操作的数据结构映射对应之前记录的跨度值，最简单的方式就是另外建一个栈同步操作
从代码书写简便的角度，我选择了第二种，你也可以尝试下用第一种方法来实现下
class StockSpanner {
private Stack<Integer> priceStack;
private Stack<Integer> spanStack;
public StockSpanner() {
priceStack = new Stack<>();
spanStack = new Stack<>();
}
public int next(int price) {
int span = 1;
while (!priceStack.isEmpty() && priceStack.peek() <= price){
priceStack.pop();
span += spanStack.pop();
}
priceStack.add(price);
spanStack.add(span);
return span;
}
}
Java的Stack运行效率比较慢，单当前这个场景下如果追求速度，可以考虑下自建一个简单快速点的栈数据结构，这里只讨论本题的思路，不在这个上面继续做扩展了
https://leetcode.cn/problems/online-stock-span/solution/by-cheungq-6-bd6u/