算法训练营（day59）
单调栈原理
单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是只需要遍历一次。
在使用单调栈的时候首先要明确如下几点：
- 单调栈里存放的元素是什么？
单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
- 单调栈里元素是递增呢？ 还是递减呢？
注意一下顺序为 从栈头到栈底的顺序，这里我们要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，加入一个元素i，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。
单调栈判断条件
- 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
42. 接雨水
题目链接：https://leetcode.cn/problems/trapping-rain-water/description/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解题思路
解题过程：单调栈
- 解题的关键在于：压入栈的元素应该是 从大到小 的，当当前压入的元素比栈顶大时，则说明出现凹坑可以接雨水。
- 设置单调栈的判断条件
height[index] < height[stackTop]，直接压栈height[index] = height[stackTop]，将栈顶元素弹出，再进行压栈height[index] > height[stackTop]，说明当前栈顶元素是坑底，需要计算长宽进行计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int stackTop = stack.peek();
if(height[index] < height[stackTop]){
stack.push(index);
}else if(height[index] == height[stackTop]){
stack.pop();
stack.push(index);
}else{
int heightAtIdx = height[index];
while(!stack.isEmpty() && (heightAtIdx > height[stackTop])){
int mid = stack.pop();
if(!stack.isEmpty()){
int left = stack.peek();
int h = Math.min(height[left], height[index]) - height[mid];
int w = index - left - 1;
int hold = h * w;
if(hold > 0){
sum += hold;
}
stackTop = stack.peek();
}
}
stack.push(index);
}
|
- 累加得出的凹坑面积，即可获得最大接雨水量
详细代码
双指针法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int trap(int[] height) {
int sum = 0;
for(int i = 0; i < height.length; i++){
if(i == 0 || i == height.length - 1){
continue;
}
int leftHeight = height[i];
int rightHeight = height[i];
for(int r = i; r < height.length; r++){
if(height[r] > rightHeight){
rightHeight = height[r];
}
}
for(int l = i - 1; l >= 0; l--){
if(height[l] > leftHeight){
leftHeight = height[l];
}
}
int h = Math.min(leftHeight, rightHeight) - height[i];
if(h > 0){
sum += h;
}
}
return sum;
}
}
|
动态规划：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int trap(int[] height) {
int len = height.length;
if(len < 2){
return 0;
}
int[] maxLeft = new int[len];
int[] maxRight = new int[len];
maxLeft[0] = height[0];
for(int i = 1; i < len; i++){
maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
}
maxRight[len - 1] = height[len - 1];
for(int i = len - 2; i >= 0; i--){
maxRight[i] = Math.max(height[i], maxRight[i + 1]);
}
int sum = 0;
for(int i = 0; i < len; i++){
int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
if(count > 0){
sum += count;
}
}
return sum;
}
}
|
单调栈：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public int trap(int[] height) {
int size = height.length;
if(size < 2){
return 0;
}
Stack<Integer> stack = new Stack<>();
stack.push(0);
int sum = 0;
for(int index = 1; index < size; index ++){
int stackTop = stack.peek();
if(height[index] < height[stackTop]){
stack.push(index);
}else if(height[index] == height[stackTop]){
stack.pop();
stack.push(index);
}else{
int heightAtIdx = height[index];
while(!stack.isEmpty() && (heightAtIdx > height[stackTop])){
int mid = stack.pop();
if(!stack.isEmpty()){
int left = stack.peek();
int h = Math.min(height[left], height[index]) - height[mid];
int w = index - left - 1;
int hold = h * w;
if(hold > 0){
sum += hold;
}
stackTop = stack.peek();
}
}
stack.push(index);
}
}
return sum;
}
}
|
84. 柱状图中最大的矩形
题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
解题思路
解题过程：单调栈
- 解题的关键在于：压入栈的元素应该是 从大到小 的，当当前压入的元素比栈顶大时，则说明出现当前获得的最大矩形可以扩容。
- 设置单调栈的判断条件
height[index] < height[stackTop]，直接压栈height[index] = height[stackTop]，将栈顶元素弹出，再进行压栈height[index] > height[stackTop]，说明当前栈顶元素是矩形的最小宽，矩形的长可以扩容至 height[index]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| if(heights[i] > heights[stack.peek()]){
stack.push(i);
}else if(heights[i] == heights[stack.peek()]){
stack.pop();
stack.push(i);
}else{
while(heights[i] < heights[stack.peek()]){
int mid = stack.peek();
stack.pop();
int left = stack.peek();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = Math.max(result, w * h);
}
stack.push(i);
}
|
- 累加得出的矩形面积，即可获得最大矩形面积
详细代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int[] newHeight = new int[heights.length + 2];
newHeight[0] = 0;
newHeight[newHeight.length - 1] = 0;
for(int i = 0; i < heights.length; i++){
newHeight[i + 1] = heights[i];
}
heights = newHeight;
stack.push(0);
int result = 0;
for(int i = 1; i < heights.length; i++){
if(heights[i] > heights[stack.peek()]){
stack.push(i);
}else if(heights[i] == heights[stack.peek()]){
stack.pop();
stack.push(i);
}else{
while(heights[i] < heights[stack.peek()]){
int mid = stack.peek();
stack.pop();
int left = stack.peek();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = Math.max(result, w * h);
}
stack.push(i);
}
}
return result;
}
}
|
