亚马逊没有网站怎么做seo,广州南站在哪个区,招标采购平台,做平面设计需要学什么软件739. 每日温度
输入一个数组#xff0c;找比i天温度高的第一天
知识点#xff1a;单调栈 状态#xff1a;看思路自己写 思路#xff1a;
看自己写的注释#xff0c;维护一个单调栈
// 版本一
class Solution {
public:vectorint dailyTemperatures(vector…739. 每日温度
输入一个数组找比i天温度高的第一天
知识点单调栈 状态看思路自己写 思路
看自己写的注释维护一个单调栈
// 版本一
class Solution {
public:vectorint dailyTemperatures(vectorint T) {// 递减栈// 从栈头往栈底看是递增stackint st;vectorint result(T.size(), 0); // 栈中存的是位置st.push(0);for (int i 1; i T.size(); i) {if (T[i] T[st.top()]) { // 情况一当前数字比栈顶小直接入栈st.push(i);} else if (T[i] T[st.top()]) { // 情况二当前数字相等直接入栈因为题目只求比他大st.push(i);} else {// 情况三当前数字比栈顶大更新result[st.top()] i - i - st.top();//也就是更新距离更新后出栈// 继续看新一个栈顶//直到不再比栈顶大了或者栈为空入栈while (!st.empty() T[i] T[st.top()]) { // 情况三result[st.top()] i - st.top();st.pop();}st.push(i);}}// 遍历完数组后如还有元素在栈里说明之后没有比他大的了所以初始化为0return result;}
};496. 下一个更大元素 I
知识点单调栈 状态不会 思路
在卡哥代码上加了注释 // 直接查找nums2的下一个最大元素但在查找时加一个判断看num1中是不是有这个 // 有的话写在res的对应位置中通过哈希
// 版本一
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {stackint st;vectorint result(nums1.size(), -1);if (nums1.size() 0) return result;unordered_mapint, int umap; // key:下标元素value下标for (int i 0; i nums1.size(); i) {umap[nums1[i]] i;}st.push(0);// 直接查找nums2的下一个最大元素但在查找时加一个判断看num1中是不是有这个// 有的话写在res的对应位置中通过哈希for (int i 1; i nums2.size(); i) {if (nums2[i] nums2[st.top()]) { // 情况一st.push(i);} else if (nums2[i] nums2[st.top()]) { // 情况二st.push(i);} else { // 情况三while (!st.empty() nums2[i] nums2[st.top()]) {if (umap.count(nums2[st.top()]) 0) { // 看map里是否存在这个元素int index umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下表result[index] nums2[i];}st.pop();}st.push(i);}}return result;}
};
