文章目录
一、42、接雨水二、84、柱状图中最大的矩形三、完整代码
所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。
一、42、接雨水
思路分析：本题使用单调栈的方法，寻找数组当中的一个元素，左边最大元素和右边最大元素，来计算雨水面积。从栈头（弹出元素的那一端）到栈底的顺序是从小到大的顺序。一旦发现添加的柱子元素高度大于栈头元素时，可以视为找到了一个右边最大元素的柱子，那么栈头元素就是中间的凹槽部分，随后将栈头元素弹出，更新后栈的栈头元素就是左边柱子。根据短板效应，雨水的面积取决于左右柱子当中较短的那根柱子。因此，将左右两边柱子高度取小值，然后减去中间凹槽的高度，高度乘以宽度就是雨水的面积。
int h = min(height[st.top()], height[i]) - height[mid]; // 左右两边柱子高度取小，然后减去中间凹槽的高度
int w = i - st.top() - 1;
程序如下：
class Solution {
public:
int trap(vector
if (height.size() <= 2) return 0;
stack
st.push(0);
int sum = 0;
for (int i = 1; i < height.size(); i++) {
while (!st.empty() && height[i] > height[st.top()]) { // height[i]为右边柱子
int mid = st.top(); // 中间的凹槽
st.pop(); // 此时的st.top()为左边柱子
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;
}
};
复杂度分析：
时间复杂度：
O
(
n
)
O(n)
O(n)。空间复杂度：
O
(
n
)
O(n)
O(n)。
二、84、柱状图中最大的矩形
思路分析：本题可以将矩形的面积抽象成三部分，它是由左边柱子，右边柱子，和中间柱子组成的，和接雨水的思路类似。不过本题需要寻找的是每个柱子左右两边第一个小于该柱子的柱子，因此从栈头到栈底的顺序应该是从大到小。每当是新的元素小于当前栈顶元素说明找到了右边柱子，可以计算面积，面积=w*h，计算出的面积和之前的值进行比较，取最大值。while()循环加上st.pop()是要对数组中的元素进行循环比较，不断改变高度h以便求出最大值。此外，防止数组是单调递增或者是单调递减数组，需要在heights数组的前后分别插入0。 程序如下：
class Solution2 {
public:
int largestRectangleArea(vector
int result = 0;
stack
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
for (int i = 1; i < heights.size(); i++) {
while (heights[i] < heights[st.top()]) { // height[i]为右边柱子
int mid = st.top(); // 中间柱子
st.pop(); // 此时的st.top()为左边柱子
int w = i - st.top() - 1;
int h = heights[mid];
result = max(result, w * h);
}
st.push(i);
}
return result;
}
};
复杂度分析：
时间复杂度：
O
(
n
)
O(n)
O(n)。空间复杂度：
O
(
n
)
O(n)
O(n)。
三、完整代码
# include
# include
# include
using namespace std;
class Solution {
public:
int trap(vector
if (height.size() <= 2) return 0;
stack
st.push(0);
int sum = 0;
for (int i = 1; i < height.size(); i++) {
while (!st.empty() && height[i] > height[st.top()]) { // height[i]为右边柱子
int mid = st.top(); // 中间的凹槽
st.pop(); // 此时的st.top()为左边柱子
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;
}
};
class Solution2 {
public:
int largestRectangleArea(vector
int result = 0;
stack
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
for (int i = 1; i < heights.size(); i++) {
while (heights[i] < heights[st.top()]) { // height[i]为右边柱子
int mid = st.top(); // 中间柱子
st.pop(); // 此时的st.top()为左边柱子
int w = i - st.top() - 1;
int h = heights[mid];
result = max(result, w * h);
}
st.push(i);
}
return result;
}
};
int main()
{
//Solution s1;
//vector
//int result = s1.trap(height);
Solution2 s2;
vector
int result = s2.largestRectangleArea(heights);
cout << result << endl;
system("pause");
return 0;
}
end
好文链接
您阅读本篇文章共花了： 大家都在找：
算法：算法具有传递性特征对吗
发表评论