Problem: 901. Online Stock Span 股票价格跨度
两个数组的，一个用来存放数字，另一个用来存放每个数字符合条件的区间开始和结束索引，对每个next放入的数字，若数字数组最后一个数字<=price，则只需要从索引对数组最后拿到起始索引，从起始索引开始向前寻找就行，不需要每次都遍历一次，避免了重复查找带来的消耗
Code
class StockSpanner { public: vector<int> tr; vector<pair<int, int>> pr; StockSpanner() { } int next(int price) { if(tr.size() == 0) { tr.push_back(price); pr.push_back({0, 0}); return 1; } else { if(tr.back() <= price) { int start = pr.back().first; int i; for(i = start - 1; i >= 0; i--) { if(tr[i] > price) { break; } } pr.push_back({i+1, tr.size()}); tr.push_back(price); return pr.back().second - pr.back().first + 1; } else { pr.push_back({tr.size(), tr.size()}); tr.push_back(price); return 1; } } return 1; } }; /** * Your StockSpanner object will be instantiated and called as such: * StockSpanner* obj = new StockSpanner(); * int param_1 = obj->next(price); */
