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

本文主要是介绍代码随想录算法训练营day62 | 42. 接雨水、84.柱状图中最大的矩形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

42. 接雨水

暴力解法

遍历每根柱子(第一个和最后一个不需要遍历，因为不可能存住水)，找到当前柱子的左边最高柱子lHeight，右边最高柱子rHeight，当前柱子能存的水为min(min(lHeight, rHeight) - 当前柱子的高度, 0)

class Solution:def trap(self, height: List[int]) -> int:result = 0for i in range(1, len(height)-1):leftHeight = height[i]rightHeight = height[i]for j in range(i):leftHeight = max(leftHeight, height[j])for j in range(i+1, len(height)):rightHeight = max(rightHeight, height[j])result += min(leftHeight, rightHeight) - height[i]return result

会超时

双指针解法

是对暴力解法的优化，暴力法在求当前柱子的左右最高的柱子时都会遍历一遍数组，而我们可以提前计算每个柱子的左右最高的柱子，存储起来。

如何求每个柱子的左右最高的柱子？其实和暴力法一样，左右最高的柱子如果比height[i]低或相等，肯定是存不在水的，因此可以初始化为height[i]，即本方法中可以和本身也比较一次高度

• 从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
• 从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);

class Solution:def trap(self, height: List[int]) -> int:if len(height) <= 2:return 0maxLeftHeight = [0] * len(height)maxRightHeight = [0] * len(height)maxLeftHeight[0] = height[0]for i in range(1, len(height)):maxLeftHeight[i] = max(maxLeftHeight[i-1], height[i])maxRightHeight[-1] = height[-1]for i in range(len(height)-2, -1, -1):maxRightHeight[i] = max(maxRightHeight[i+1], height[i])result = 0for i in range(1, len(height)-1):result += min(maxLeftHeight[i], maxRightHeight[i]) - height[i]return result

单调栈解法

本题使用单调栈有如下几个问题：

• 1、首先单调栈是按照行方向来计算雨水
• 2、使用单调栈内元素的顺序
• 从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
• 3、遇到相同高度的柱子怎么办？遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。
• 4、栈里要保存什么数值？栈里就存放下标就行

三种情况

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

先将下标0的柱子加入到栈中，st.push(0);。 栈中存放我们遍历过的元素，所以先将下标0加进来。然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)。

如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。

如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。

如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了。

class Solution:def trap(self, height: List[int]) -> int:if len(height) <= 2:return 0result = 0stack = [0]for i in range(1, len(height)):if height[i] < height[stack[-1]]:stack.append(i)elif height[i] == height[stack[-1]]:stack.pop()stack.append(i)else:while stack and height[i] > height[stack[-1]]:mid = stack.pop()if stack:result += (min(height[stack[-1]], height[i]) - height[mid]) * (i-stack[-1]-1)stack.append(i)return result

如果当前遍历的元素（柱子）高度等于栈顶元素的高度，可以不更新栈顶元素，直接入栈即可。后续计算出栈逻辑时，因为凹槽左边的值和当前值相同，计算值为0，和更新栈顶后结果一致。简化版代码就是这个逻辑

还有一个要注意的点：

原始的时候0入栈了，后来无论怎么操作最后当前元素都会入栈，栈内至少有一个元素，所以不需要判断栈内是否存在元素。

为什么当前元素大于栈顶元素的时候会检查？因为while语句下弹出元素，可能不止一个，因此需要判断。

精简版

class Solution:def trap(self, height: List[int]) -> int:if len(height) <= 2:return 0result = 0stack = [0]for i in range(1, len(height)):while stack and height[i] > height[stack[-1]]:mid = stack.pop()if stack:result += (min(height[stack[-1]], height[i]) - height[mid]) * (i-stack[-1]-1)stack.append(i)return result

84. 柱状图中最大的矩形

暴力解法

找到每根柱子左边和右边第一个小于当前柱子高度的 w = right - left - 1; h = heights[i]; result = max(result, w * h);

双指针解法

是对暴力解法的优化，和接雨水有差别，在求每根柱子左边和右边第一个小于当前柱子高度，不是直接和前一个进行比较，而是使用while不断迭代。数组中存储的是索引。

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:leftMin = [0] * len(heights)rightMin = [0] * len(heights)leftMin[0] = -1for i in range(1, len(heights)):j = i - 1while j != -1 and heights[j] >= heights[i]:j = leftMin[j] leftMin[i] = jrightMin[-1] = len(heights)for i in range(len(heights)-1, -1, -1):j = i + 1while j != len(heights) and heights[j] >= heights[i]:j = rightMin[j]rightMin[i] = jresult = 0for i in range(len(heights)):result = max(result, heights[i] * (rightMin[i] - leftMin[i] - 1))return result

单调栈

因为本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序

输入数组首尾各补上一个0（与接雨水不同的是，本题原首尾的两个柱子可以作为核心柱进行最大面积尝试）

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.insert(0, 0)heights.append(0)stack = [0]result = 0for i in range(1, len(heights)):if heights[i] > heights[stack[-1]]:stack.append(i)elif heights[i] == heights[stack[-1]]:stack.pop()stack.append(i)else:while stack and heights[i] < heights[stack[-1]]:mid = stack.pop()if stack:result = max((i - stack[-1] - 1) * heights[mid], result)stack.append(i)return result

精简版，stack不可能为空，因为数组第一个元素为0，不可能有比0还小的值，题目规定heights大于等于0， 因此第一个元素一定在stack中，不需要判断stack为空

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.insert(0, 0)heights.append(0)stack = [0]result = 0for i in range(1, len(heights)):while heights[i] < heights[stack[-1]]:mid = stack.pop()result = max((i - stack[-1] - 1) * heights[mid], result)stack.append(i)return result

这篇关于代码随想录算法训练营day62 | 42. 接雨水、84.柱状图中最大的矩形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---