LC503. 下一个更大元素Ⅱ
对于“每日温度”,相当于对nums数组,进行了两次遍历。用i % size所得余数作为下标,且循环的圈数为size * 2
vector<int> nextGreaterElements(vector<int>& nums)
{
int size = nums.size();
vector<int> result(size, -1);
vector<int> sta;
sta.push_back(0);
for (int i = 1; i < size * 2; ++i)
{
while (sta.empty() != true)
{
int temp = sta.back();
if (nums[i % size] > nums[temp])
{
result[temp] = nums[i % size];
sta.pop_back();
}
else
break;
}
sta.push_back(i % size);
}
return result;
}
LC42. 接雨水
int trap(vector<int>& height)
{
int sum = 0;
stack<int> st;
st.push(0);
for (int i = 1; i < height.size(); i++)
{
if (height[i] < height[st.top()])
{
st.push(i);
}
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[st.top()], height[i]) - height[mid];
int w = i - st.top() - 1;
sum += h * w;
}
}
st.push(i);
}
}
return sum;
}
标签:sta,LC503,nums,int,height,LC42,Day52,st,size
From: https://www.cnblogs.com/Mingzijiang/p/17279692.html