一、leetcode第503题
本题要求循环数组中下一个更大元素的值,由于数组循环设置,因此遍历时选择遍历2*nums.size(),在计算时i%nums.size(),最后求得的即为循环数组中下一个更大元素的值。
具体代码如下:
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int>st;
vector<int>result(nums.size(),-1);
st.push(0);
if(nums.size()==1)
{
return result;
}
for(int i=1;i<nums.size()*2;i++)
{
if(nums[i%nums.size()]<=nums[st.top()])
{
st.push(i%nums.size());
}
else
{
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;
}
};
二、leetcode第42题
本题要求接雨水的最大体积,因此需要设置单调栈,计算体积时要知道凹槽的宽度与高度,宽度就是栈中下标的差值再减一,高度则是凹槽左右两边高度的最小值减去凹槽底部的高度,其余操作与单调栈操作一致,最后求出的就是能接雨水的最大值。
具体代码如下:
class Solution {
public:
int trap(vector<int>& height) {
stack<int>st;
int result=0;
st.push(0);
for(int i=1;i<height.size();i++)
{
if(height[i]<height[st.top()])
{
st.push(i);
}
else if(height[i]==height[st.top()])
{
st.pop();
st.push(i);
}
else
{
while(!st.empty()&&height[i]>height[st.top()])
{
int mid=st.top();
st.pop();
if(!st.empty())
{int h=min(height[i],height[st.top()])-height[mid];
result+=h*(i-st.top()-1);}
}
st.push(i);
}
}
return result;
}
};