国内设计网站,织梦怎么制作手机网站,企业搜索,中核华兴建设有限公司投标网站理解题目#xff0c;对于第 i 天#xff0c;要求的是前 i - 1 天所满足条件的跨度
思路#xff1a;
暴力搜索的方式是#xff0c;对于每一个第 i 天都遍历搜索 i - 1#xff0c; i - 2#xff0c;…#xff0c;直到第 j 天大于当前价格优化#xff0c;考虑哪里进行了… 理解题目对于第 i 天要求的是前 i - 1 天所满足条件的跨度
思路
暴力搜索的方式是对于每一个第 i 天都遍历搜索 i - 1 i - 2…直到第 j 天大于当前价格优化考虑哪里进行了重复搜索或者说第 i 天的跨度计算后是否可以用于后面某一天的跨度计算显然如果第 j 天的跨度是 nj i那么当对于第 i 天遍历搜索到第 j 天时如果第 i 天的价格大于等于第 j 天那么第 i 天的跨度可以直接加上 n这样可以省去 n 次的重复判断下一个判断就从 j - n 天开始
代码单调栈实现
class StockSpanner:def __init__(self):self.l [[1000000, 0]]def next(self, price: int) - int:if price self.l[-1][0]:self.l.append([price, 1])return 1ans 1while price self.l[-1][0]:ans self.l[-1][1]self.l.pop()self.l.append([price, ans])return ans
