宁波创建网站,杭州市城乡建设网官网,江苏省建设厅网站施工员证查询,phpcms 手机网站总结leetcode75中的单调栈算法题解题思路。 上一篇#xff1a;力扣75——区间集合 力扣75——单调栈 1 每日温度2 股票价格跨度1 - 2 解题总结 1 每日温度
题目#xff1a;
给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer 力扣75——区间集合 力扣75——单调栈 1 每日温度2 股票价格跨度1 - 2 解题总结 1 每日温度
题目
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中
answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都
不会升高请在该位置用 0 来代替。题解 单调栈。 进出栈策略for循环遍历对于当前的气温先跟栈顶比较如果大于栈顶则计算栈顶与当前的天数间隔并出栈然后继续比较直到不大于最后将当前气温的日期进栈。
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {int n temperatures.size();vectorint ans(n);stackint s;for (int i 0; i n; i) {while (!s.empty() temperatures[i] temperatures[s.top()]) {int previousIndex s.top();ans[previousIndex] i - previousIndex;s.pop();}s.push(i);}return ans;}
};2 股票价格跨度
题目
设计一个算法收集某些股票的每日报价并返回该股票当日价格的 跨度 。当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数从今天开始
往回数包括今天。例如如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]那么股票跨度将是
[1,1,1,2,1,4,6] 。实现 StockSpanner 类StockSpanner() 初始化类对象。
int next(int price) 给出今天的股价 price 返回该股票当日价格的跨度。题解 单调栈。 进出栈策略先把一个非常大的数压入栈中然后for循环遍历。对于当天的股价先跟栈顶比较如果大于等雨栈顶则计算栈顶与当前的天数间隔并出栈然后继续比较直到小于最后将当前股价及其日期进栈。
class StockSpanner {
public:StockSpanner() {this-stk.emplace(-1, INT_MAX);this-idx -1;}int next(int price) {idx;while (price stk.top().second) {stk.pop();}int ret idx - stk.top().first;stk.emplace(idx, price);return ret;}private:stackpairint, int stk; int idx;
};1 - 2 解题总结
问题特点1每个数据都有时间戳、数据间有大小差异。 问题特点2向后查找对于某个时间节点的数据查找其与之后的第几个数据满足某个比较条件向前查找对于某个时间节点的数据查找其与之前的第几个数据满足某个比较条件。 向后查找由于遍历时还未知道后面的数据所以当前数据只是用来计算前面的数据的结果然后它再进栈。 向前查找由于遍历时已经知道当前的数据所以当前数据是可以得到结果的至于当前数据是否需要进栈则需要根据题目具体要求进行判断。
