代码随想录Day16 单调栈
739. 每日温度
该题的题意很简单 要求遍历温度数组 找出几天后会出现下一次更高的温度 这就可以用到单调栈的知识
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了
那么我们该如何实现单调栈呢 该题目栈内保存的肯定是元素的下标 因为这样相减就可以得到几天后会出现更高的温度 0先放入栈底 然后遍历到74 通过栈顶的下标找到栈顶元素是73 因为74大于73所以ans数组下标为栈顶的下标放入1-0=1 一次类推 如果遍历的元素小于等于栈顶的元素 就要一次入栈 满足单调栈为单调递增的时候 可以求出数组右边第一个大于自己元素的位置
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> st;
vector<int> ans(temperatures.size(),0);
st.push(0);
for(int i=1;i<temperatures.size();i++){
if(temperatures[i]<=temperatures[st.top()]){
st.push(i);
}else{
while(!st.empty()&& temperatures[i]>temperatures[st.top()]){
ans[st.top()]=i-st.top();
st.pop();
}
st.push(i);
}
}
return ans;
}
};496.下一个更大元素 I
这一题也是单调栈的思路 不过会比较绕一点 首先给我们两个数组 我们要遍历nums1 然后让在nums2找到元素出现的位置 找到下一个更大元素的位置 返回的是元素本身
首先我们返回的数组是和nums1是一样大的 然后我们可以把nums1放到map里面映射 key为下标元素 value为下标 然后再遍历nums2数组 首先判断该元素和栈顶元素的大小 如果大于栈顶元素 再判断栈顶元素有没有在nums1里面出现过 如果出现过在ans数组value位置赋值上该元素
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> st;
vector<int> ans(nums1.size(),-1);
if(nums1.size()==0) return ans;
unordered_map<int,int> umap;
for(int i=0;i<nums1.size();i++){
umap[nums1[i]]=i;
}
st.push(0);
for(int i=0;i<nums2.size();i++){
while(!st.empty() && nums2[i]>nums2[st.top()]){
if(umap.find(nums2[st.top()])!=umap.end()){
int index=umap[nums2[st.top()]];
ans[index]=nums2[i];
}
st.pop();
}
st.push(i);
}
return ans;
}
};503.下一个更大元素II
这一题就是把数组变成了一个xun'huan'shu'z
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
for (int i = 0; i < nums.size() * 2; i++) {
// 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
return result;
}
};42.接雨水
这一题就是对单调栈的应用了 题意很明确 就是利用高度差形成的凹槽我们才可以计算能接到多少的雨水
所以在我们遍历元素的时候 我们需要知道该元素 左边第一个比他大的元素和右边第一个比他大的元素 我们知道求解右边第一个比自己的大元素的时候 我们用的是单调递增的单调栈 所以当遍历元素大于栈顶元素的时候 说明中间的凹槽就是栈顶元素 遍历元素是右边大于它的 那么左边元素肯定是之前遍历过的 根据单调栈的特性 就是栈顶元素的下一个元素
如果当遍历元素等于栈顶元素 我们先弹出再入栈和直接入栈的结果是一样的 计算思路会有所不同 如果直接入栈 就相当于左边的元素和自己一样大 形成高度差为0 计算结果就是0 此结果和弹出栈的结果是一样的
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
st.push(0);
int sum=0;
for(int i=1;i<height.size();i++){
while(!st.empty() && height[i]>height[st.top()]){
int mid=st.top();
st.pop();
if(!st.empty()){
int h=min(height[st.top()],height[i])-height[mid];
int w=i-st.top()-1;
sum+=h*w;
}
}
st.push(i);
}
return sum;
}
};84.柱状图中最大的矩形
这一题思路和接雨水类似 不过该题是求 左右两边小于自己的元素 我们用单调递减栈就可以实现这个功能 左边比自己小的元素就在栈顶元素的下一位 但是与接雨水不同的是 我们这一题需要在数组的首尾加上0这个元素 因为我们必须在出现两边都有比自己小的元素的时候才会开始计算结果 避免了单调数组带来的影响
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.insert(heights.begin(),0);
heights.push_back(0);
st.push(0);
int ans=0;
for(int i=0;i<heights.size();i++){
while(!st.empty() && heights[i]<heights[st.top()]){
int mid=st.top();
st.pop();
int w=i-st.top()-1;
int h=heights[mid];
ans=max(ans,h*w);
}
st.push(i);
}
return ans;
}
};
原文地址：https://blog.csdn.net/m0_73740071/article/details/142423236
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！