Day 59 单调栈
503. 下一个更大元素II
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int len = nums.size();
nums.insert(nums.end(), nums.begin(), nums.end());
vector<int> descStk, rst(len, -1);
for (int i = 0; i < nums.size(); ++i)
{
while (!descStk.empty() && nums[descStk.back()] < nums[i])
{
int idx = descStk.back() % len;
if (rst[idx] == -1)
{
rst[idx] = nums[i];
}
descStk.pop_back();
}
descStk.push_back(i);
}
return rst;
}
};
其实也可以不扩充nums,而是在遍历的过程中模拟走了两边nums
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int len = nums.size();
vector<int> descStk, rst(len, -1);
for (int i = 0; i < len * 2; ++i)
{
int modI = i % len;
while (!descStk.empty() && nums[descStk.back()] < nums[modI])
{
int idx = descStk.back() % len;
if (rst[idx] == -1)
{
rst[idx] = nums[modI];
}
descStk.pop_back();
}
descStk.push_back(modI);
}
return rst;
}
};
42. 接雨水
三种方法都写了一遍
暴力方法
逐列计算
找到当前位置,左边最高的柱子的索引和右边最高的柱子的索引,两者中相对小的那个,将去当前位置的高度,就是水柱的高度,而宽度是1
超时了
class Solution {
public:
int trap(vector<int>& height) {
int sum = 0;
for (int i = 1; i < height.size() - 1; i++)
{
int leftTaller, rightTaller;
leftTaller = rightTaller = height[i];
for (int j = i - 1; j >= 0; --j)
{
if (height[j] > leftTaller)
{
leftTaller = height[j];
}
}
for (int j = i + 1; j < height.size(); ++j)
{
if (height[j] > rightTaller)
{
rightTaller = height[j];
}
}
sum += min(leftTaller, rightTaller) - height[i];
}
return sum;
}
};
双指针
提前记录好左边最高的和右边最高的索引
class Solution {
public:
int trap(vector<int>& height) {
vector<int> maxLeft(height.size()), maxRight(height.size());
maxLeft[0] = height[0];
for (int i = 1; i < height.size(); ++i)
{
maxLeft[i] = max(height[i], maxLeft[i - 1]);
}
maxRight.back() = height.back();
for (int i = height.size() - 2; i >= 0; --i)
{
maxRight[i] = max(height[i], maxRight[i + 1]);
}
int sum = 0;
for (int i = 1; i < height.size() - 1; i++)
{
sum += min(maxLeft[i], maxRight[i]) - height[i];
}
return sum;
}
};
暴力方法和双指针都是按照列的方式进行计算的文章来源:https://www.toymoban.com/news/detail-624036.html
单调栈
而单调栈的方式是按照行的方式进行计算的,在思考的时候要记得这一点区别文章来源地址https://www.toymoban.com/news/detail-624036.html
class Solution {
public:
int trap(vector<int>& height) {
int sum = 0;
stack<int> stk;
stk.push(0);
for (int i = 0; i < height.size(); ++i)
{
if (height[i] < height[stk.top()])
{
stk.push(i);
}
else if (height[i] == height[stk.top()])
{
stk.pop();
stk.push(i);
}
else
{
while (!stk.empty() && height[i] > height[stk.top()])
{
int idx = stk.top();
stk.pop();
if (!stk.empty())
{
int w = i - stk.top() - 1;
int h = min(height[i], height[stk.top()]) - height[idx];
sum += w * h;
}
}
stk.push(i);
}
}
return sum;
}
};
到了这里,关于算法刷题Day 59 下一个更大元素II+接雨水的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!