每日算法刷题Day57:8.6:leetcode 单调栈6道题，用时2h
一.基础
1.套路
1.需要计算nums[i]的下一个更大/更小的下标/值(需要map映射)，或者计算离的有多远/一个区间有多长[[七.单调栈#6. 853. 车队(中等)]][[七.单调栈#6. 853. 车队(中等,学习)]]
2.及时去掉无用数据，保证栈中元素有序。
3.可分为两种情况，针对找右边的数，从右往左遍历就是存储下一个更大的数，从左往右遍历(跟找的顺序一样的好写) 就是存储未找到下一个更大的数的数
找左边的数反着来
(1)从右往左遍历
栈中存储下一个更大的数
class Solution {public: vector dailyTemperatures(vector& temperatures) { int n = temperatures.size(); vector res(n, 0); vector stk; // 从右往左遍历 for (int i = n - 1; i >= 0; --i) { // 维护单调性 while (!stk.empty() && temperatures[stk.back()] <= temperatures[i]) stk.pop_back(); // 存在下一个更大的数 if (!stk.empty()) res[i] = stk.back() - i; // 不存在下一个更大的数 else res[i] = 0; stk.push_back(i); } return res; }};2.从左往右遍历(习惯写这个，符合思维)
栈中存储未找到下一个更大的数的数
class Solution {public: vector dailyTemperatures(vector& temperatures) { int n = temperatures.size(); vector res(n, 0); vector stk; // 从左往右遍历 for (int i = 0; i < n; ++i) { // 当前遍历元素是之前的下一个更大的数 while (!stk.empty() && temperatures[stk.back()] < temperatures[i]) { res[stk.back()] = i - stk.back(); stk.pop_back(); } // 放入当前元素 stk.push_back(i); } // 最后处理仍未找到下一个更大的数的数 for(int& x:stk) res[x]=temperatures[x]; return res; }};2. 题目描述
3. 学习经验
1.计算nums[i]的下一个更大/更小的值时需要map映射[[七.单调栈#3. 496. 下一个更大元素I(简单,学习)]]
2.看清楚是找右边的数还是找左边的数[[七.单调栈#5. 901. 股票价格跨度(中等)]]
3.栈中元素可以为pair
4.单调栈本质是在维护几个独立的区间，每个区间都是有序的，但在栈中只留下极值元素[[七.单调栈#6. 853. 车队(中等,学习)]],所以其他元素在遍历的时候视作无用元素，要弹出栈，这些区间的划分肯定是有序的，所以栈是单调的。且每个区间在遍历的时候只有一个元素就能算当前区间长度了[[七.单调栈#5. 901. 股票价格跨度(中等)]]
1. 739. 每日温度(中等,学习)
739. 每日温度 - 力扣（LeetCode）
思想
1.给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
2.写法一:从右到左遍历
栈中元素为下一个更大的数，如下图所示，当前从右遍历到5，比2和3都大，5左边的数右侧更大的数如果可以为2和3，那必定取5，所以2和3被移出栈
![[每日温度从右往左.jpg]]
3.写法二：从左到右遍历
栈中元素为没有找到下一个更大的数的数，如下图所示从左到右遍历到5，然后遍历2，5还未找到下一个更大的数，所以5不能出栈
![[每日温度从左往右.jpg]]
代码
1.从右往左遍历
class Solution {public: vector dailyTemperatures(vector& temperatures) { int n = temperatures.size(); vector res(n, 0); vector stk; // 从右往左遍历 for (int i = n - 1; i >= 0; --i) { // 维护单调性 while (!stk.empty() && temperatures[stk.back()] <= temperatures[i]) stk.pop_back(); // 存在下一个更大的数 if (!stk.empty()) res[i] = stk.back() - i; // 不存在下一个更大的数 else res[i] = 0; stk.push_back(i); } return res; }};2.从左往右遍历
class Solution {public: vector dailyTemperatures(vector& temperatures) { int n = temperatures.size(); vector res(n, 0); vector stk; // 从左往右遍历 for (int i = 0; i < n; ++i) { // 当前遍历元素是之前的下一个更大的数 while (!stk.empty() && temperatures[stk.back()] < temperatures[i]) { res[stk.back()] = i - stk.back(); stk.pop_back(); } // 放入当前元素 stk.push_back(i); } return res; }};2. 1475. 商品折扣后的最终价格(简单)
1475. 商品折扣后的最终价格 - 力扣（LeetCode）
思想
1.给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
代码
class Solution {public: vector finalPrices(vector& prices) { int n = prices.size(); vector res(n, 0); vector stk; for (int i = 0; i = prices[i]) { res[stk.back()] = prices[stk.back()] - prices[i]; stk.pop_back(); } stk.push_back(i); } for (int& x : stk) res[x] = prices[x]; return res; }};3. 496. 下一个更大元素I(简单,学习)
496. 下一个更大元素 I - 力扣（LeetCode）
思想
1.nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
2.需要计算 nums2[i]的下一个更大元素的值 ，所以是单调栈。因为这题nums1是nums2的子集，所以就可以遍历nums2,通过判断当前元素在不在nums1中来决定入不入栈。但因为是值，所以还需要一个 **map映射nums1的值-下标 **
代码
class Solution {public: vector nextGreaterElement(vector& nums1, vector& nums2) { int n1 = nums1.size(), n2 = nums2.size(); vector res(n1, -1); map idxs; // nums1值-下标 for (int i = 0; i < n1; ++i) idxs[nums1[i]] = i; vector stk; for (int& x : nums2) { while (!stk.empty() && x > stk.back()) { res[idxs[stk.back()]] = x; stk.pop_back(); } // 如果x在nums1中 if (idxs.find(x) != idxs.end()) stk.push_back(x); } return res; }};4. 503.下一个更大元素II(中等)
503. 下一个更大元素 II - 力扣（LeetCode）
思想
1.给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
2.循环就想到遍历两次，然后下标取余即可。但是每个元素下标还是只入一次栈，因为只更新一次答案
代码
class Solution {public: vector nextGreaterElements(vector& nums) { int n = nums.size(); vector res(n, -1); vector stk; for (int i = 0; i nums[stk.back()]) { res[stk.back()] = nums[i % n]; stk.pop_back(); } if (i < n) stk.push_back(i); } return res; }};5. 901. 股票价格跨度(中等)
901. 股票价格跨度 - 力扣（LeetCode）
思想
1.设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
- 例如，如果未来 7 天股票的价格是
[100,80,60,70,60,75,85]，那么股票跨度将是[1,1,1,2,1,4,6]。
实现StockSpanner类： StockSpanner()初始化类对象。int next(int price)给出今天的股价price，返回该股票当日价格的 跨度 。
2.这题是找左边的数,所以按道理来说从右往左栈储存未找到答案的数的数更好写，但是题目要从左往右一个一个输入，然后一个一个输出，只能从左往右栈储存下一个更小的数，但因为是连续日数，所以要记录左边比当前价格低的数的最大连续日数，进行累加
3.优化建议:这题要计算当前price离上一个更大元素有多远，所以比它小的直接出栈，他们是无用元素，因为要算距离，所以要记录下标，且还要知道值，可以用数组+索引变量+栈，也可以用pair栈+索引变量来解决
代码
class StockSpanner {public: vector prices; // 记录值 vector cnts; // 记录日数 int id; // 当前遍历下标 vector stk; StockSpanner() { prices.clear(); id = 0; } int next(int price) { int cnt = 1; while (!stk.empty() && !prices.empty() && price >= prices[stk.back()]) { cnt += cnts[stk.back()]; stk.pop_back(); } prices.push_back(price); stk.push_back(id); cnts.push_back(cnt); ++id; return cnt; }};/** * Your StockSpanner object will be instantiated and called as such: * StockSpanner* obj = new StockSpanner(); * int param_1 = obj->next(price); */优化:
class StockSpanner {public: typedef pair PII; // 索引-值 vector stk; int id; StockSpanner() { stk.clear(); id = 0; } int next(int price) { while (!stk.empty() && price >= stk.back().second) { stk.pop_back(); } // 为空为[0,id] int res = id + 1; // (stk.back().first,id] if (!stk.empty()) res = id - stk.back().first; stk.push_back({id, price}); ++id; return res; }};/** * Your StockSpanner object will be instantiated and called as such: * StockSpanner* obj = new StockSpanner(); * int param_1 = obj->next(price); */6. 853. 车队(中等,学习)
853. 车队 - 力扣（LeetCode）
思想
1.在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。
给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。
一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。
车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。
即便一辆车在 target 才赶上了一个车队，它们仍然会被视作是同一个车队。
返回到达目的地的车队数量 。
2.这题要算车队数，那怎么样能算作一个车队呢，即看各车辆单独到目的地的时间，如果处在一个区间即为一个车队，而这个区间是单调递增的，表示前面的车比后面的车快，最后剩下几个区间就是几个车队。而维护一个区间从左往右遍历就是当前时间比栈顶元素时间长，则移除无用元素，只算当前时间一个车队。
但是这个从左到右遍历是以距离为度量的，所以得先把题目数组按照距离升序，考虑有两个元素，直接用结构体更方便。
代码
class Solution {public: struct Node { int pos; int spe; Node(int _pos, int _spe) : pos(_pos), spe(_spe) {} // 按位置排序 bool operator<(const Node& other) { return pos < other.pos; } }; vector nodes; int carFleet(int target, vector& position, vector& speed) { int n = position.size(); for (int i = 0; i < n; ++i) { Node node(position[i], speed[i]); nodes.push_back(node); } // 按位置排序 sort(nodes.begin(), nodes.end()); vector times(n); // 算时间 for (int i = 0; i < n; ++i) { times[i] = 1.0 * (target - nodes[i].pos) / nodes[i].spe; } vector stk; for (int i = 0; i = stk.back()) { stk.pop_back(); } stk.push_back(times[i]); } return stk.size(); }};
