第十章 单调栈part02
42. 接雨水
接雨水这道题目是 面试中特别高频的一道题，也是单调栈 应用的题目，大家好好做做。
建议是掌握 双指针 和单调栈，因为在面试中 写出单调栈可能 有点难度，但双指针思路更直接一些。
在时间紧张的情况有，能写出双指针法也是不错的，然后可以和面试官在慢慢讨论如何优化。
文章讲解
暴力解法
- 使用列来计算，宽度一定是1，只用把高度求出来即可
- 每一列雨水的高度，取决于，该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。
-
比如求列4的雨水高度，如图：image.png
列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。
列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。
列4 柱子的高度为1（以下用height表示）
那么列4的雨水高度为 列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。
列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。
此时求出了列4的雨水体积。
虽然这个解法超时了
class Solution {
public int trap(int[] height) {
int sum = 0;
int len = height.length;
// 第一个柱子和最后一个柱子不接雨水
for(int i = 0; i < len; i++){
// 第一个柱子和最后一个柱子不接雨水
if(i == 0 || i == len - 1) continue;
int rHeight = height[i]; // 记录右边柱子的最高高度
int lHeight = height[i]; // 记录左边柱子的最高高度
// 找右边最高的柱子
for(int r = i + 1; r < len; 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 = Math.min(lHeight, rHeight) - height[i];
if(h > 0) sum += h;
}
return sum;
}
}
双指针优化
当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。
即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);
class Solution {
public int trap(int[] height) {
int sum = 0;
int len = height.length;
int[] leftMax = new int[len];
int[] rightMax = new int[len];
leftMax[0] = height[0];
for(int i = 1; i < len - 1; i++) leftMax[i] = Math.max(height[i], leftMax[i-1]);
rightMax[len - 1] = height[len - 1];
for(int j = len - 2; j >= 0; j--) rightMax[j]= Math.max(height[j], rightMax[j+1]);
for(int i = 0; i < len; i++){
// 计算当前柱子上能接的雨水
int h = Math.min(leftMax[i], rightMax[i]) - height[i];
if(h > 0) sum += h;
}
return sum;
}
}
单调栈解法
准备工作
- 首先单调栈是按照行方向来计算雨水
- 使用单调栈内元素的顺序：从栈顶到栈底是从小到大，因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
- 遇到相同高度的柱子怎么办。
遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。 - 栈里要保存什么数值
使用单调栈，也是通过 长 * 宽 来计算雨水面积的。
长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，栈里就存放下标就行，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了。
单调栈处理逻辑
先将下标0的柱子加入到栈中，st.push(0);。 栈中存放我们遍历过的元素，所以先将下标0加进来。
然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)。
以下逻辑主要就是三种情况
情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。-
情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]
取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]（就是图中的高度1）。
此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]（就是图中的高度2）。
当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3）。
image.png
此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的元素，三个元素来接水！
那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[st.top()], height[i]) - height[mid];
雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - st.top() - 1 ;
当前凹槽雨水的体积就是：h * w。
class Solution {
public int trap(int[] height) {
int sum = 0;
int len = height.length;
if(len <= 2) return 0;
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i = 1; i < len; i++){
if(height[i] < height[stack.peek()]){ // 情况一
stack.push(i);
}else if (height[i] == height[stack.peek()]){ // 情况二
stack.pop();
stack.push(i);
}else{
while(!stack.isEmpty() && height[i] > height[stack.peek()]){ // 情况三
int mid = stack.pop();
if(!stack.isEmpty()){
int left = stack.peek();
int h = Math.min(height[left], height[i]) - height[mid];
int w = i - left - 1;
int hold = h * w;
if(hold > 0) sum += hold;
}
}
stack.push(i);
}
}
return sum;
}
}
class Solution {
public int trap(int[] height) {
int sum = 0;
int len = height.length;
if(len <= 2) return 0;
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i = 1; i < len; i++){
while(!stack.isEmpty() && height[i] > height[stack.peek()]){ // 情况三
int mid = stack.pop();
// stack.pop(); 不能有这一行，可能导致stack为空
if(!stack.isEmpty()){
int left = stack.peek();
int h = Math.min(height[left], height[i]) - height[mid];
int w = i - left - 1;
int hold = h * w;
if(hold > 0) sum += hold;
}
}
stack.push(i);
}
return sum;
}
}
84. 柱状图中最大的矩形
双指针解法
本题要记录记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。
所以需要循环查找，也就是下面在寻找的过程中使用了while。
class Solution {
public int largestRectangleArea(int[] heights) {
//双指针
int len = heights.length;
int[] minLeftIndex = new int[len];
int[] minRightLeft = new int[len];
Arrays.fill(minLeftIndex, -1);
Arrays.fill(minRightLeft, len);
// 记录每个柱子左边第一个小于该柱子的下标
for(int i = 1; i < len; i++){
int t = i - 1;
while(t >= 0 && heights[t] >= heights[i]){
t = minLeftIndex[t];
}
minLeftIndex[i] = t;
}
// 记录每个柱子右边第一个小于该柱子的下标
for(int j = len - 2; j >= 0; j--){
int t = j + 1;
while(t < len && heights[t] >= heights[j]){
t = minRightLeft[t];
}
minRightLeft[j] = t;
}
int result = 0;
for(int i = 0; i < len; i++){
int sum = heights[i] * (minRightLeft[i] - minLeftIndex[i] - 1);
result = Math.max(sum, result);
}
return result;
}
}
单调栈
42. 接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。
这里就涉及到了单调栈很重要的性质，就是单调栈里的顺序，是从小到大还是从大到小。
因为本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序
主要就是分析清楚如下三种情况：
情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
- 此外，在 height数组上前后，都加了一个元素0
- 结尾加0的原因：因为如果数组本身就是升序的，例如[2,4,6,8]，那么入栈之后 都是单调递减，一直都没有走 情况三 计算结果的哪一步，所以最后输出的就是0了。
那么结尾加一个0，就会让栈里的所有元素，走到情况三的逻辑。 - 开头加元素0的原因：如果数组本身是降序的，例如 [8,6,4,2]，在 8 入栈后，6 开始与8 进行比较，此时我们得到 mid（8），rigt（6），但是得不到 left。
因为 将 8 弹出之后，栈里没有元素了，那么为了避免空栈取值，直接跳过了计算结果的逻辑。
之后又将6 加入栈（此时8已经弹出了），然后 就是 4 与 栈口元素 8 进行比较，周而复始，那么计算的最后结果resutl就是0。
class Solution {
public int largestRectangleArea(int[] heights) {
//单调栈
int len = heights.length;
Deque<Integer> st = new LinkedList<>();
// Add 0 at the beginning and end of the array
int[] modifiedHeights = new int[len + 2];
int moLen = modifiedHeights.length;
int result = 0;
System.arraycopy(heights, 0, modifiedHeights, 1, len);
modifiedHeights[0] = 0;
modifiedHeights[moLen - 1] = 0;
st.push(0);
for(int i = 1; i < moLen; i++){
if(modifiedHeights[i] > modifiedHeights[st.peek()]){ // Situation 1
st.push(i);
}else if(modifiedHeights[i] == modifiedHeights[st.peek()]){ // Situation 2
st.pop();
st.push(i);
}else{
while(!st.isEmpty() && modifiedHeights[i] < modifiedHeights[st.peek()]){
int mid = st.pop();
if(!st.isEmpty()){
int left = st.peek();
int right = i;
int width = right - left - 1;
int height = modifiedHeights[mid];
result = Math.max(result, width * height);
}
}
st.push(i);
}
}
return result;
}
}
System.arraycopy(heights, 0, modifiedHeights, 1, heights.length);
heights: 原始数组，这里的元素将会被复制。
0:开始复制的索引位置。在这个例子中，是从 heights 数组的索引 0 开始复制。
modifiedHeights:目标数组，也就是复制后的元素将被放置在这里。
1:在目标数组 modifiedHeights 中开始放置元素的位置。这里是从索引 1 开始放置。
heights.length: 要复制的元素数量。这里是要复制整个 heights 数组的长度。
