文章目录

一、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& height) {

if (height.size() <= 2) return 0;

stack st; // 存着下标,计算的时候用下标对应的柱子高度

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& heights) {

int result = 0;

stack st; // 存着下标,计算的时候用下标对应的柱子高度

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& height) {

if (height.size() <= 2) return 0;

stack st; // 存着下标,计算的时候用下标对应的柱子高度

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& heights) {

int result = 0;

stack st; // 存着下标,计算的时候用下标对应的柱子高度

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 height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };

//int result = s1.trap(height);

Solution2 s2;

vector heights = { 2, 1, 5, 6, 2, 3 };

int result = s2.largestRectangleArea(heights);

cout << result << endl;

system("pause");

return 0;

}

end

好文链接

评论可见,请评论后查看内容,谢谢!!!
 您阅读本篇文章共花了: