C language force buckle question 42 of rain. Four methods - violence, dynamic planning, stack, double pointer

Given n Nonnegative integers indicate that each width is 1 Height map of columns of , Calculate columns arranged in this way , How much rain can be received after rain .

Example 1：

Input ：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output ：6
explain ： Above is an array of [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Height map of representation , under these circumstances , Can connect 6 Units of rain （ The blue part indicates rain ）.

Example 2：

Input ：height = [4, 2, 0, 3, 2, 5]
Output ：9

Tips ：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Pass times 531, 609
Submit the number 863, 255

source ： Power button （LeetCode）
link ：https ://leetcode.cn/problems/trapping-rain-water
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1： violence

Intuitive ideas

Directly follow the problem description . For each element in the array , We find the highest position that water can reach after rain , Equal to the smaller value of the maximum height on both sides minus the value of the current height .

Algorithm

1. initialization ans=0
2. Scan the array from left to right ：
   initialization max_left=0
   Scan left from the current element and update ：max_left=max⁡(max_left,height[j])
   Scan right from the current element and update ：max_right=max⁡(max_right,height[j])
   take min⁡(max_left,max_right)−height[i] Add up to ans

The time complexity is large, which is O（n^2）

Method 2： Dynamic programming

Intuitive ideas

In violent methods , We scan left and right every time just to find the maximum value . But we can store this value in advance . therefore , It can be solved by dynamic programming .

Algorithm

1.     Find subscript from array i To the height of the highest bar at the leftmost end left_max
2.     Find subscript from array i To the height of the highest bar block at the rightmost end right_max.
3.     Scan array height And update the answer ：
4.     Add up min⁡(max_left[i],max_right[i])−height[i] To ans On

The time and space complexity are O（n）

Method 3： Stack

Intuitive ideas

We don't have to do things like this 2 That stores the maximum height , Instead, the stack is used to track the longest bar of water that could be stored . Using the stack, you can complete the calculation in a single traversal .

We maintain a stack while traversing arrays . If the current bar is less than or equal to the top of the stack , We stack the index of the bar block , This means that the current bar is defined by the previous bar in the stack . If we find a bar block longer than the top of the stack , We can make sure that the bar at the top of the stack is defined by the current bar and the previous bar on the stack , So we can pop up the top of the stack and add up the answers to ans

Algorithm

1. Use the stack to store the index subscripts of bar blocks .
2. Traversal array ：
   - When the stack is not empty and height[current]>height[st.top()]：
       It means that the elements in the stack can be ejected . Pop up top element top;
       Calculate the distance between the current element and the top element , Prepare for filling ;distance=current−st.top()−1
       Find the defined height
       bounded_height=min⁡(height[current],height[st.top()])−height[top]
       Add water accumulation to the answer ans+=distance×bounded_height
   - Subscript the current index onto the stack
   - take current Move to the next position

The complexity of time and space is the same as that of method two .

Method 4： Use double pointer

Intuitive ideas

And methods 2 comparison , We don't calculate separately from left and right , We find a way to complete the traversal at one time .
as long as right_max[i]>left_max[i], The height of ponding will be determined by left_max decision , Similarly left_max[i]>right_max[i]
So we can think that if there is a higher bar at one end （ For example, right end ）, The height of the ponding depends on the height of the current direction （ From left to right ）. When we find the other side （ On the right side ） The bar height of is not the highest , We start traversing in the opposite direction （ From right to left ）.
We must maintain... While traversing left_max and right_max , But now we can use two pointers alternately , Realization 1 It can be completed in times of traversal .

Here is the code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>


int trap(int* height, int heightSize) 
{
	int ans = 0;
	int left = 0;
	int right = heightSize - 1;
	int premax = 0;
	int max = 0;
	int i = 0;
	while (left < right)
	{
		if (height[left] > height[right] && height[right] > max)
		{
			premax = max;
			max = height[right];
			for (i = left + 1; i <= right - 1; i++)
			{
				if (height[i] <= premax)
					ans = ans - premax + max;
				if (height[i] > premax&&height[i] < max)
					ans = ans + max - height[i];
			}
			right--;
		}

		if (height[left] <= height[right] && height[left] > max)
		{
			premax = max;
			max = height[left];
			for (i = left + 1; i <= right - 1; i++)
			{
				if (height[i] <= premax)
					ans = ans - premax + max;
				if (height[i] > premax&&height[i] < max)
					ans = ans + max - height[i];
			}
			left++;
		}

		if (height[left] <= max)
		{
			left++;
		}
		if (height[right] <= max)
		{
			right--;
		}
	}
	return ans;
}

int main()
{
	int height[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
	int heightSize = sizeof(height) / sizeof(int);
	int ans = trap(height, heightSize);
	printf("%d", ans);
}