网站提交链接入口,我们提供的网站建设,wordpress插件安装不,软件开发公司排行榜901. 股票价格跨度
题意
设计一个数据结构返回股票当日价格的跨度#xff08;必须是当日开始的#xff09;
解法 暴力 优化
一开始没理解题意#xff0c;以为是求第 i 天及以前#xff0c;小于等于 prices[i] 的最大连续子串的长度。后来才发现#xff0c;这个最大连…901. 股票价格跨度
题意
设计一个数据结构返回股票当日价格的跨度必须是当日开始的
解法 暴力 优化
一开始没理解题意以为是求第 i 天及以前小于等于 prices[i] 的最大连续子串的长度。后来才发现这个最大连续子串必须包含当天。
所以问题就转换成了从右往左寻找第一个大于 prices[i] 的数。
第一个想法是暴力。也就是对于每一天从右往左遍历寻找第一个大于 prices[i] 的数。 但是注意数据范围为 O ( n 5 ) O(n^5) O(n5) 并且调用操作的数量级为 O ( n 4 ) O(n^4) O(n4)而暴力的时间复杂度为 O ( n 2 ) O(n^2) O(n2)必定超时。
需要进行优化。既然要优化那么 能够利用的只有当天以前的答案因为每一天都要计算答案是动态累积的。
设数组 prices[] 维护股票每一天的价格数组 spans[] 维护每一天的答案。又注意到若 s p a n s [ i ] k spans[i] k spans[i]k那么也就是说 p r i c e s [ i − k 1 ] − p r i c e s [ i ] prices[i - k 1] - prices[i] prices[i−k1]−prices[i] 都将小于等于 p r i c e s [ i ] prices[i] prices[i]也就是说 s p a n s [ i ] spans[i] spans[i] 实际上维护了一个区间的最大值。
那么假设股票的当天价格为 p r i c e price price从右向左遍历数组 prices[]:
如果 p r i c e s [ i ] p r i c e prices[i] price prices[i]price那么 s p a n s [ i ] spans[i] spans[i] 维护的这样一个区间都将小于等于 p r i c e price price所以将其并入如果 p r i c e s [ i ] p r i c e prices[i] price prices[i]price那么这个最大连续子串被截断此时 最大连续子串的长度就是要求返回的答案。
class StockSpanner {
public:StockSpanner() {}int next(int price) {int ans 1, tmp 0;int idx prices.size() - 1;if(idx -1){prices.emplace_back(price);spans.emplace_back(1);return 1;}if(prices[idx] price){ans max(ans, tmp);idx--;tmp 0;}else{if(idx prices.size() - 1) tmp 1;while(idx 0 prices[idx] price){tmp spans[idx];idx - spans[idx];}}ans max(ans, tmp);prices.emplace_back(price);spans.emplace_back(ans);return ans;}
private:vectorint prices, spans;
};/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner* obj new StockSpanner();* int param_1 obj-next(price);*/复杂度
时间复杂度不会算 ) 空间复杂度不会算 ) 解法2 单调栈
由于这道题的本质就是寻找 p r i c e price price 左侧第一个大于 p r i c e price price 的元素所以显然可以使用单调递减栈来解答。
为了获取跨度再在栈中存储一个 i d x idx idx 信息。
class StockSpanner {
public:StockSpanner(): size(0) {}int next(int price) {pairint, int cur(price, size);pairint, int tmp(0, 0);while(!st.empty() st.top().first price) st.pop();if(!st.empty()) tmp st.top();st.push(cur);return cur.second - tmp.second;}
private:stackpairint, int st;int size;
};/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner* obj new StockSpanner();* int param_1 obj-next(price);*/复杂度
时间复杂度 O ( n ) O(n) O(n)。 空间复杂度 O ( n ) O(n) O(n)。
文章转载自： http://www.morning.lclpj.cn.gov.cn.lclpj.cn http://www.morning.zqbrw.cn.gov.cn.zqbrw.cn http://www.morning.twwts.com.gov.cn.twwts.com http://www.morning.ydxx123.cn.gov.cn.ydxx123.cn http://www.morning.inheatherskitchen.com.gov.cn.inheatherskitchen.com http://www.morning.bgbnc.cn.gov.cn.bgbnc.cn http://www.morning.bxbkq.cn.gov.cn.bxbkq.cn http://www.morning.yhjrc.cn.gov.cn.yhjrc.cn http://www.morning.xzqzd.cn.gov.cn.xzqzd.cn http://www.morning.kpgft.cn.gov.cn.kpgft.cn http://www.morning.mnnxt.cn.gov.cn.mnnxt.cn http://www.morning.ksgjy.cn.gov.cn.ksgjy.cn http://www.morning.tfpqd.cn.gov.cn.tfpqd.cn http://www.morning.npcxk.cn.gov.cn.npcxk.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.mkyxp.cn.gov.cn.mkyxp.cn http://www.morning.nssjy.cn.gov.cn.nssjy.cn http://www.morning.mkzdp.cn.gov.cn.mkzdp.cn http://www.morning.kttbx.cn.gov.cn.kttbx.cn http://www.morning.kdlzz.cn.gov.cn.kdlzz.cn http://www.morning.rlqwz.cn.gov.cn.rlqwz.cn http://www.morning.rbjp.cn.gov.cn.rbjp.cn http://www.morning.jppb.cn.gov.cn.jppb.cn http://www.morning.gstg.cn.gov.cn.gstg.cn http://www.morning.bmhc.cn.gov.cn.bmhc.cn http://www.morning.kspfq.cn.gov.cn.kspfq.cn http://www.morning.hyhqd.cn.gov.cn.hyhqd.cn http://www.morning.xdxpq.cn.gov.cn.xdxpq.cn http://www.morning.grfhd.cn.gov.cn.grfhd.cn http://www.morning.shuanga.com.cn.gov.cn.shuanga.com.cn http://www.morning.ztfzm.cn.gov.cn.ztfzm.cn http://www.morning.rfbt.cn.gov.cn.rfbt.cn http://www.morning.tmfhx.cn.gov.cn.tmfhx.cn http://www.morning.yxgqr.cn.gov.cn.yxgqr.cn http://www.morning.rnngz.cn.gov.cn.rnngz.cn http://www.morning.rlksq.cn.gov.cn.rlksq.cn http://www.morning.wwnb.cn.gov.cn.wwnb.cn http://www.morning.rgpbk.cn.gov.cn.rgpbk.cn http://www.morning.ljbm.cn.gov.cn.ljbm.cn http://www.morning.mdpcz.cn.gov.cn.mdpcz.cn http://www.morning.sfphz.cn.gov.cn.sfphz.cn http://www.morning.qypjk.cn.gov.cn.qypjk.cn http://www.morning.lrplh.cn.gov.cn.lrplh.cn http://www.morning.thwhn.cn.gov.cn.thwhn.cn http://www.morning.wplbs.cn.gov.cn.wplbs.cn http://www.morning.qcrhb.cn.gov.cn.qcrhb.cn http://www.morning.pffx.cn.gov.cn.pffx.cn http://www.morning.rfbq.cn.gov.cn.rfbq.cn http://www.morning.jfbrt.cn.gov.cn.jfbrt.cn http://www.morning.tlpgp.cn.gov.cn.tlpgp.cn http://www.morning.rszbj.cn.gov.cn.rszbj.cn http://www.morning.kpyyf.cn.gov.cn.kpyyf.cn http://www.morning.pjwrl.cn.gov.cn.pjwrl.cn http://www.morning.ddqdl.cn.gov.cn.ddqdl.cn http://www.morning.rtpw.cn.gov.cn.rtpw.cn http://www.morning.pmysp.cn.gov.cn.pmysp.cn http://www.morning.sbrpz.cn.gov.cn.sbrpz.cn http://www.morning.ykrkb.cn.gov.cn.ykrkb.cn http://www.morning.tjsxx.cn.gov.cn.tjsxx.cn http://www.morning.c7622.cn.gov.cn.c7622.cn http://www.morning.ljxxl.cn.gov.cn.ljxxl.cn http://www.morning.hwxxh.cn.gov.cn.hwxxh.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.wfyqn.cn.gov.cn.wfyqn.cn http://www.morning.yxdrf.cn.gov.cn.yxdrf.cn http://www.morning.cljmx.cn.gov.cn.cljmx.cn http://www.morning.bbgr.cn.gov.cn.bbgr.cn http://www.morning.zwgbz.cn.gov.cn.zwgbz.cn http://www.morning.pfcrq.cn.gov.cn.pfcrq.cn http://www.morning.tkfnp.cn.gov.cn.tkfnp.cn http://www.morning.sqqdy.cn.gov.cn.sqqdy.cn http://www.morning.xpqdf.cn.gov.cn.xpqdf.cn http://www.morning.rjcqb.cn.gov.cn.rjcqb.cn http://www.morning.rgzc.cn.gov.cn.rgzc.cn http://www.morning.mntxalcb.com.gov.cn.mntxalcb.com http://www.morning.xkzr.cn.gov.cn.xkzr.cn http://www.morning.lbssg.cn.gov.cn.lbssg.cn http://www.morning.jpkk.cn.gov.cn.jpkk.cn http://www.morning.nqwkn.cn.gov.cn.nqwkn.cn http://www.morning.krgjc.cn.gov.cn.krgjc.cn
