单调栈
文章目录
- 一、每日温度
- 二、下一个更大元素 I
- 总结
一、每日温度
1.暴力解法,双层循环
2.单调栈,递增排列,分三种情况。1.当前元素大于栈顶元素,得到结果,弹出并压入。2.当前元素小于等于栈顶元素,压入栈
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
//暴力解法,双层循环
stack<int>st;
st.push(0);
vector<int>result(temperatures.size(), 0);
for (int i = 1; i < temperatures.size(); i++) {
if (temperatures[i] < temperatures[st.top()]) {
st.push(i);
}
else if (temperatures[i] == temperatures[st.top()]) {
st.push(i);
}
else {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
};
二、下一个更大元素 I
1.暴力解法,双层循环
2.单调栈,map哈希记录nums1出现的元素,nums2使用单调栈类似于每日温度,当出现大于情况是,判断栈顶元素是否出现在map中,是则获取结果,弹出栈。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
//暴力解法,一层遍历num1,一层遍历
vector<int>result(nums1.size(), -1);
for (int i = 0; i < nums1.size(); i++) {
int flag = 0;
for (int j = 0; j < nums2.size(); j++) {
if (nums2[j] == nums1[i]) {
flag = j;
break;
};
}
for (int k = flag; k < nums2.size(); k++) {
if (nums2[k] > nums2[flag]) {
result[i] = nums2[k];
break;
}
}
}
return result;
}
};
总结
单调栈有助于降低时间复杂度
学习时间90min。
学习资料:《代码随想录》。