当前位置：首页 > news >正文

Studying-代码随想录训练营day49| 42. 接雨水、84.柱状图中最大的矩形

news 来源：原创 2024/9/22 4:16:21

第49天，单调栈part02，两个很经典的例题，编程语言：C++

42. 接雨水

84.柱状图中最大的矩形

总结：

42. 接雨水

文档讲解：代码随想录接雨水

视频讲解：手撕接雨水

题目： 42. 接雨水 - 力扣（LeetCode）

学习：本题是非常巧妙的一道题，首先第一个重点是要理解题意，凹槽是存在左边比自己高，右边也比自己高的位置。本题有两个计算思路：按行计算和按列计算。

按照行计算：

按照列计算：

1.我们首先考虑按列计算的方法：按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了。（要注意第一个柱子和最后一个柱子是不接雨水的）

找到每个柱子左边和右边的最高柱子有两个办法：

①暴力求解：通过一个for循环，遍历当前柱子，两个for循环找到左边和右边最高的柱子，最后选取最小的柱子即可。

//时间复杂度O(n^2)
//空间复杂度O(1)
class Solution {
public:int trap(vector<int>& height) {int sum = 0;for (int i = 0; i < height.size(); i++) {// 第一个柱子和最后一个柱子不接雨水if (i == 0 || i == height.size() - 1) continue;int rHeight = height[i]; // 记录右边柱子的最高高度int lHeight = height[i]; // 记录左边柱子的最高高度for (int r = i + 1; r < height.size(); r++) {if (height[r] > rHeight) rHeight = height[r];}for (int l = i - 1; l >= 0; l--) {if (height[l] > lHeight) lHeight = height[l];}int h = min(lHeight, rHeight) - height[i];if (h > 0) sum += h;}return sum;}
};

②我们也可以采用双指针的方法，提前预处理好每个点左右最高的柱子，然后进行求解，能够降低时间复杂度。

//时间复杂度O(n)3n
//空间复杂度O(n)
class Solution {
public:int trap(vector<int>& height) {if (height.size() <= 2) return 0;vector<int> maxLeft(height.size(), 0);vector<int> maxRight(height.size(), 0);int size = maxRight.size();// 记录每个柱子左边柱子最大高度maxLeft[0] = height[0];for (int i = 1; i < size; i++) {maxLeft[i] = max(height[i], maxLeft[i - 1]);}// 记录每个柱子右边柱子最大高度maxRight[size - 1] = height[size - 1];for (int i = size - 2; i >= 0; i--) {maxRight[i] = max(height[i], maxRight[i + 1]);}// 求和int sum = 0;for (int i = 0; i < size; i++) {int count = min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) sum += count;}return sum;}
};

2.除此之外，我们还可以考虑行计算的方式，采用的是单调栈的方法。

基于行计算，我们可以发现，如果从栈顶到栈底是从小到大的排列顺序的话。那么一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。下图给一个例子：

假如遇到相同的柱子，我们肯定需要把当前柱子加入栈中，前一个值相同的柱子可以选择去掉也可可以原则保留，对结果没有影响。因为我们计算的时候，左边柱子如果和本身一样的话，实际上最后求得的高度是0。

单调栈处理逻辑：

情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]

我们需要针对这三种情况进行处理：

代码：

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int largestRectangleArea(vector<int>& heights) {if(heights.size() == 1) return heights[0];int result = 0; //记录结果stack<int> st; //单调栈，加入的是已经遍历的元素//我们需要首尾加0或者-1来完成首尾元素的遍历heights.insert(heights.begin(), 0); //头部加0heights.push_back(0); //尾部加0//我们需要找多左右第一个小于当前的值st.push(0);for(int i = 1; i < heights.size(); i++) {if(heights[i] > heights[st.top()]) { //从栈顶到栈底是递减的st.push(i);}else if(heights[i] == heights[st.top()]) {st.pop(); //也可以不加这个，只是要多计算一次0st.push(i);}else {while(!st.empty() && heights[i] < heights[st.top()]) { //此处需要循环，不断找到合适的数值int mid = st.top();st.pop();if(!st.empty()) {int h = heights[mid];int w = i - st.top() - 1;result = max(result, h * w);}} st.push(i); //注意每一次都需要把当前下标加入}}return result;}
};

84.柱状图中最大的矩形

文档讲解：代码随想录柱状图中最大的矩形

视频讲解：手撕柱状图中最大的矩形

题目：代码随想录柱状图中最大的矩形

学习：本题实际上和上一题是一样的，上一题是找左右最大值，而本题则是找左右的最小值。每一个柱都可以向左右扩展到比它小的柱的位置。因此本题和上一题的唯一区别就在于，本题找的是左右的最小值，而上一题找的是左右的最大值。

因此本题的暴力解法和双指针优化方法和上一题的逻辑基本相同，再次就不过多赘述，我们主要讲解单调栈的方法。

由于本题是求解左右的最小值，因此本题单调栈里元素的顺序，从栈顶到栈底应该是从大到小的顺序！可以发现栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度。

因此单调栈的处理逻辑的顺序也需要发生改变：

情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

本题还需要注意一点，是需要在头部和尾部加一个0，用来处理第一个柱形和最后一个柱形。例如如果没有在末尾加0的话，针对[2,4,6,8]的情况，我们就没办法找到最大的矩形8。

头部加0也是如此，为了处理第一个元素，防止其没有左边界。这是与上一题不同的，因为上一题不需要考虑下标0的左端和最后一个元素的右端。最后可以得到代码：

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int largestRectangleArea(vector<int>& heights) {if(heights.size() == 1) return heights[0];int result = 0; //记录结果stack<int> st; //单调栈，加入的是已经遍历的元素//我们需要首尾加0或者-1来完成首尾元素的遍历heights.insert(heights.begin(), 0); //头部加0heights.push_back(0); //尾部加0//我们需要找多左右第一个小于当前的值st.push(0);for(int i = 1; i < heights.size(); i++) {if(heights[i] > heights[st.top()]) { //从栈顶到栈底是递减的st.push(i);}else if(heights[i] == heights[st.top()]) {st.pop(); //也可以不加这个，只是要多计算一次0st.push(i);}else {while(!st.empty() && heights[i] < heights[st.top()]) { //此处需要循环，不断找到合适的数值int mid = st.top();st.pop();if(!st.empty()) {int h = heights[mid];int w = i - st.top() - 1;result = max(result, h * w);}} st.push(i); //注意每一次都需要把当前下标加入}}return result;}
};